下载掌阅APP，畅读海量书库
立即打开
暴力搜索法有两种：向上标记法和同步前进法。
从 u 向上一直到根节点，标记所有经过的节点；若 v 已被标记，则 v 节点为LCA( u , v )；否则 v 也向上走，第1次遇到已标记的节点时，该节点为LCA( u , v )。
将 u、v 中较深的节点向上走到和深度较浅的节点同一深度，然后两个点一起向上走，直到走到同一个节点，该节点就是 u、v 的最近公共祖先，记作LCA( u , v )。若较深的节点 u 到达 v 的同一深度时，那个节点正好是 v ，则 v 节点为LCA( u , v )。
以暴力搜索法求解LCA，两种方法的时间复杂度在最坏情况下均为 O ( n )。