什么是公共祖先？

祖先指的是树上结点的n到树的根结点路径上的所有除自身以外的所有结点都是结点n的祖先，包括根节点。

而公共祖先就是两个树上结点到根结点路径上的相同结点。

 

最近公共祖先：

两个树上结点i，j到根结点路径上的相同结点中，找一个结点k，使得i->k + j->k的和最小。

 

如何求得最近公共祖先？

暴力枚举：遍历两个树上结点到根节点路径上的所有结点，从根节点开始比较找到最后一个公共结点即为最近公共祖先。

暴力枚举显然是可以的，但是复杂度太高了，若一棵树退化成了一条链，最坏复杂度会变成树的结点数n，而若查询的次数规模为m，则复杂度为O(nm)。

 

优化枚举，用倍增代替枚举。

若要从结点i到根节点的路径上和结点j到根结点的路径上，找一个公共祖先x，我们可以遍历寻找，也可以根据深度利用倍增寻找。

结点i，j之间有两种情况，一种为i的深度和j的深度不等，另一种为i的深度和j的深度相等。

若深度不等则找到较长路径中深度相同的点，将不等深度化为相等深度，这样就能将两种情况变化为一种情况处理。

 

已知点i的深度，而i的祖先的深度显然是小于i的深度的。

若i，j的深度为k，假设k = 7，二进制数表示为000111，则可以找寻 i和 j到根结点路径中深度为2^2的值是否相等。

若相等则说明 x在深度 k到 2^2之间。

若不等则说明 x在深度 2^2到根节点之间。

若相等则找寻深度为2^1的值，因为2^1在深度2^2到k之间。

若不等则将结点 i，结点j 跳到深度为2^2的结点，作为新的结点寻找最近公共祖先。

 

如果一个问题需要寻找到达相同目的地路径中距离最近的公共点，则可以考虑最近公共祖先的解法。