我尝试使用 Tarjan 算法和网站上的一种算法来解决这个问题：http://discuss.techinterview.org/default.asp?interview.11.532716.6 http://discuss.techinterview.org/default.asp?interview.11.532716.6，但没有一个是明确的。也许我的递归概念没有正确建立。请用小示范来解释以上两个例子。我对 Union Find 数据结构有一个想法。
这看起来很有趣的问题。所以无论如何都必须解码这个问题。准备面试。
如果存在任何其他逻辑/算法，请分享。
LCA 算法尝试做一件简单的事情：找出从两个相关节点到根的路径。现在，这两条路径将具有公共后缀（假设路径在根处结束）。 LCA 是后缀开始的第一个节点。
考虑下面的树：
r *
/ \
s * *
/ \
u * * t
/ / \
* v * *
/ \
* *
为了找到 LCA(u, v)，我们按如下步骤进行：
- 从 u 到 root 的路径： Path(u, r) = usr
- 从 v 到根的路径： Path(v, r) = vtsr
现在，我们检查常见后缀：
- 常见后缀：'sr'
- 因此 LCA(u, v) = 后缀的第一个节点 = s
注意实际的算法do not一直到根。他们使用不相交集数据结构在到达 s 时停止。
解释了一组优秀的替代方法.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
