最近公共祖先（LCA）主要算法：

1）向上标记法：

从x向上走到根节点，并标记所有经过的节点。

从y向上走到根节点，当第一次遇到已标记的节点时，就找到了LCA（x,y）.

2）树上倍增法：

树上倍增法是一个很重要的算法。除了求LCA之外，他在很多问题中都有广泛应用。设F[x,k]表示x的2^k倍祖先，即从x走向根节点走2^k步到达的节点。特别地，若该节点不存在，则令F[x,y]=0。F[x,0]就是x的父节点。除此之外，任意k属于[1,logn],F[x,k]=F[F[x,k-1],k-1]。

这类似于一个动态规划的过程，“阶段”就是节点的深度。因此，我们可以对树进行广度优先遍历，按照层次顺序，在节点入队之前，计算它在F数组中相应的值。

以上部分处理是预处理，时间复杂度是O(nlogn),之后可以多次对不同的x,y计算LCA，每次询问的时间复杂度为O(logn)

基于F数组的计算LCA(x,y)分为以下几步。

1.设d[x]表示x的深度。不妨设d[x]>=d[y]（否则可交换x,y）

2.用二进制拆分思想，把x向上调整到于y同一深度。具体来说，就是依次尝试从x向上走k=2^(logn)，……，2^1,2^0步，检查到达节点是否比y深。每次检查中，若是，则令x=F[x,y]。

3.若此时x==y，说明已经找到了LCA，LCA就等于y。

4.用二进制思想拆分，把x,y同时向上调整，并保持深度一致且二者不会相同。具体来说，就是一次尝试把x,y同时向上走k=2^(logn)，……，2^1,2^0步，若F[x,k]!=F[y,k]（即仍未相会），则令x=F[x,k],y=F[y,k]。

5.此时x，y必定只差一步就相会了，它们的父节点F[x,0]就是LCA。