如何找到二叉树中两个节点之间的距离?同样,有什么算法可以找到两个节点的最新共同祖先(最低共同祖先)?
发布于 2010-01-26 02:35:40
几乎可以肯定的是,找到共同的祖先是更容易的任务。这是一个非常简单的方法:从树的根开始,然后沿着树向下,直到到达一个节点,在这个节点上,您必须下降到不同的子节点才能到达所讨论的两个节点。该节点是公共的父节点(当然,假设树包含这两个节点)。
发布于 2010-01-26 03:39:08
这里的每个人似乎都知道,如果你记下每个节点到根的距离,那么一旦你找到了两个节点的最低公共祖先,你就可以在恒定的时间内计算出它们彼此之间的距离。
如果你只做一次与树大小成线性的工作,那么你就可以在固定的时间内找到任意两个节点的最低公共祖先(无论树有多深)。请参阅http://en.wikipedia.org/wiki/Lowest_common_ancestor
Baruch Schieber和Uzi Vishkin的最低共同祖先算法在使用和编程上是完全实用的。
发布于 2010-01-26 02:37:12
创建由每个节点的祖先组成的两个集合:当集合的并集为空时,将每个节点的下一个祖先添加到适当的列表中。一旦有了公共节点,那就是公共祖先。
https://stackoverflow.com/questions/2134583
复制相似问题