二叉树的最低共同祖先（非二叉搜索树）
我尝试使用Tarjan的算法和网站上的一种算法来解决这个问题： http ： //discuss.techinterview.org/default.asp？interview.11.532716.6 ，但没有一个是清楚的。 也许我的递归概念没有正确构建。 请举一个小型演示来解释上面两个例子。 我对Union Find数据结构有所了解。
这看起来很有意思。 所以必须解决问题无论如何。 准备面试。
如果存在任何其他逻辑/算法，请分享。
LCA算法尝试做一件简单的事情：找出从两个节点到根节点的路径。 现在，这两个路径将具有共同的后缀（假设路径在根处结束）。 LCA是后缀开始的第一个节点。
考虑以下树：
r * / \ s * * / \ u * * t / / \ * v * * / \ * *
为了找到LCA（u，v），我们按如下方式进行：
- 从u到root的路径：Path（u，r）= usr
- 从v到root的路径：Path（v，r）= vtsr
现在，我们检查公共后缀：
- 常见后缀：’sr’
- 因此，LCA（u，v）=后缀的第一个节点= s
请注意，实际的算法不会一直到根。 他们使用Disjoint-Set数据结构在到达s时停止。
这里解释了一套优秀的替代方法。
既然你提到了求职面试，我想到了这个问题的变化，你只限于O（1）内存使用。
在这种情况下，请考虑以下算法：
1）从节点u扫描树到根，找到路径长度L（u）
2）从节点v扫描树到根，找到路径长度L（v）
3）计算路径长度差D = | L（u）-L（v）|
4）从根目录中删除较长路径中的D节点
5）从两个节点并行地向上走树，直到你到达同一个节点
6）将该节点作为LCA返回
假设您只需要解决一次问题（每个数据集），那么一个简单的方法是从一个节点（连同自身）收集祖先集，然后从另一个节点中走出祖先列表，直到找到一个成员为止。上面的集合，必然是最低的共同祖先。 给出了伪代码：
Let A and B begin as the nodes in question. seen := set containing the root node while A is not root: add A to seen A := A's parent while B is not in seen: B := B's parent B is now the lowest common ancestor.
另一种方法是计算每个节点的整个路径到房间，然后从右侧扫描以查找公共后缀。 它的第一个要素是LCA。 其中哪一项更快取决于您的数据。
如果您需要找到多对节点的LCA，那么您可以进行各种空间/时间权衡：
例如，您可以预先计算每个节点的深度，这样您就可以避免每次重新创建集合（或路径），首先从较深的节点步行到较浅节点的深度，然后再行走在锁定步骤中朝向根的两个节点：当这些路径相遇时，您具有LCA。
另一种方法是使用深度模型H的下一个祖先来注释节点，这样您首先要解决类似但小时H的问题，然后解决第一个问题的H大小的实例。 这在非常深的树上是好的，并且通常选择H作为树的平均深度的平方根。