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

问题描述

我试着从工作使用的Tarjan的算法，并从网站上一种算法的问题： http://discuss.techinterview.org/default.asp?interview.11.532716.6 ，但没有很明确。也许我的递归概念无法建立正确。请给小示范讲解上面的两个例子。我有联盟的想法找到的数据结构。

这看起来很有趣的问题。因此，有脱$ C C的问题$无论如何。 preparing的采访。

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

解决方案

LCA的算法，试图做一个简单的事情：找出从问题的根源在两个节点的路径。现在，这两个路径将有一个共同的后缀（假设该路径在根部端部）。所述LCA是后缀开始处的第一个节点。

考虑下面的树：

  R *
               / \
            S * *
             / \
          U * * T
           / / \
          * V * *
             / \
            * *
 

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

• 从u路径为根：路径（U，R）= USR
• 路径从v到根：路径（V，R）= vtsr

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

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

请注意实际的算法的的没有的一路到根。他们使用不相交组数据结构，当他们到达s至停止。

这是一套优秀的替代办法解释<一个href="http://www.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29"相对=nofollow>这里。

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屋！