我尝试使用 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
现在，我们检查公共(public)后缀:
- 常用后缀:'sr'
- 因此LCA(u, v) = 后缀的第一个节点= s
请注意实际算法不会一直到根。他们使用 Disjoint-Set 数据结构在到达 s 时停止。
解释了一组优秀的替代方法 here .
关于c - 二叉树的最低公共(public)祖先(不是二叉搜索树)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3540622/