c - 二叉树的最低公共(public)祖先(不是二叉搜索树)

Question

我尝试使用 Tarjan 的算法和网站上的一种算法解决问题:http://discuss.techinterview.org/default.asp?interview.11.532716.6 ，但没有一个是明确的。也许我的递归概念没有正确建立。请举个小例子来解释上面两个例子。我对 Union Find 数据结构有所了解。

看起来很有趣的问题。所以无论如何都要解码这个问题。准备面试。

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

Answer 1

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 .