二叉树的最低共同祖先（不是二进制搜索树） [英] Lowest Common Ancestor of Binary Tree(Not Binary Search Tree)

问题描述

我尝试使用Tarjan的算法和一个来自网站的算法来解决问题： http://discuss.techinterview.org/default.asp?interview.11.532716.6 ，但没有一个是清楚的。也许我的递归概念没有正确建立。请给小说明来解释上述两个例子。我有一个关于联合查找数据结构的想法。

看起来很有趣的问题。所以不得不解码的问题无论如何。

$ b

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

解决方案

LCA算法尝试做一个简单的事情：将有问题的两个节点的路径映射到根。现在，这两个路径将具有一个共同的后缀（假设路径以root结尾）。 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时停止。

一组很好的替代方法解释为这里。

I tried working out the problem using Tarjan's Algorithm and one algorithm from the website: http://discuss.techinterview.org/default.asp?interview.11.532716.6, but none is clear. Maybe my recursion concepts are not build up properly. Please give small demonstration to explain the above two examples. I have an idea of Union Find data-structure.

It looks very interesting problem. So have to decode the problem anyhow. Preparing for the interviews.

If any other logic/algorithm exist, please share.

解决方案

The LCA algorithm tries to do a simple thing: Figure out paths from the two nodes in question to the root. Now, these two paths would have a common suffix (assuming that the path ends at the root). The LCA is the first node where the suffix begins.

Consider the following tree:

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

In order to find the LCA(u, v) we proceed as follows:

• Path from u to root: Path(u, r) = usr
• Path from v to root: Path(v, r) = vtsr

Now, we check for the common suffix:

• Common suffix: 'sr'
• Therefore LCA(u, v) = first node of the suffix = s

Note the actual algorithms do not go all the way up to the root. They use Disjoint-Set data structures to stop when they reach s.

An excellent set of alternative approaches are explained here.

这篇关于二叉树的最低共同祖先（不是二进制搜索树）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！