二叉树的最低公共祖先（不是二叉搜索树）

我试着从网站上使用Tarjan算法和一种算法来解决问题：http://discuss.techinterview.org/default.asp?interview.11.532716.6，但没有一个是清楚的。也许我的递归概念不适当地建立。请给出一个小示范来解释上述两个例子。我有联盟查找数据结构的想法。二叉树的最低公共祖先（不是二叉搜索树）

它看起来很有趣的问题。无论如何，必须解决问题。准备面试。

如果存在其他逻辑/算法，请分享。

来源

2010-08-22 AGeek

LCA算法试图做一件简单的事情：找出从问题的两个节点到根的路径。现在，这两条路径会有一个共同的后缀（假设路径以根结尾）。 LCA是后缀开始的第一个节点。

考虑下面的树：

   r * 
      /\ 
      s * * 
      /\ 
      u * * t 
     //\ 
      * v * * 
      /\ 
      * *

为了找到LCA（U，V），我们进行如下操作：

路径从u到根：路径（（v，r）= vtsr

现在，我们检查了常见的后缀：

通用后缀： 'SR'
因此LCA（U，V）=后缀的第一个节点= S

注意实际算法不要一路走到根。当它们到达s时，它们使用Disjoint-Set数据结构来停止。

一组优秀的替代方法解释为here。

来源

2010-08-22 07:57:39 dirkgently

只有一点评论：树木往往（主要）平衡。在这些情况下，使用不相交集合数据结构的开销可能比仅从u标记根，然后从v。 – Rafe 2010-08-23 03:13:40

既然你提到了工作面试，我想到了你只限于O（1）内存使用的这个问题的变化。

在这种情况下，考虑下面的算法：

1）从节点u到根扫描树，找到的路径长度L（U）

2）扫描从结点V的树（v）

3）计算路径长度差D = | L（u）-L（v）|

4）在从根部

5）走了树中从两个节点并行，直到到达同一节点

6）返回该节点作为较长路径跳过d节点LCA

来源

2010-08-22 09:16:18

-1

假设您只需要解决问题一次（每个数据集），那么一个简单的方法是从一个节点（和它自己）收集祖先集，然后从另一个节点走祖先列表直到你会发现上面一组的成员，它必然是最低的共同祖先。该伪码给出：

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。

另一种方法在depth-mod-H注释其下一个祖先的节点，以便首先解决类似但是H次小问题，然后解决第一个问题的H大小实例。这对于非常深的树木是很好的，并且通常选择H作为树的平均深度的平方根。

来源

2010-08-22 14:44:00 Ian

向上搜索第一个标记节点的根开销，如果允许，您可以做得更好预处理树。 – Ian 2010-08-22 14:48:10

二叉树的最低公共祖先（不是二叉搜索树）

回答

相关问题