algorithm - 从邻接表中找到两个节点的最低公共(public)祖先

Question

如果我知道树中每个节点的邻接列表，那么如何找出该树中存在的任意两个节点的最低公共(public)祖先？

其实我想找出任意两个节点之间的距离，所以我想计算 LCA。有没有办法从邻接表中计算出来？

T 中 n1 和 n2 的 LCA 是距离根最远的 n1 和 n2 的共享祖先。计算最低共同祖先可能是有用的，例如，作为确定树中节点对之间距离的过程的一部分:从 n1 到 n2 的距离可以计算为从根到 n1 的距离加上距离从根到 n2，减去从根到它们最低共同祖先的距离的两倍。 ( Source Wiki )

Answer 1

我们处理邻接表的事实并没有真正改变问题。

求节点A和B的LCA的基本思路如下:

• 从根开始。
• 如果 child 的子树同时包含 A 和 B，则返回该子树的 LCA。
• 如果一个 child 包含 A 而另一个 child 包含 B。

通过为任何情况返回一个指标，上述检查可以很容易地合并到一个函数中。

在无序树中，在最坏的情况下你必须探索整棵树，但在二叉搜索树中，你可以通过简单地将节点的值与当前节点进行比较来轻松检查左子树或右子树是否可以包含节点.

但实际上您不应该使用 LCA 算法来确定距离。您应该改为修改以上内容以返回距离而不是 LCA。这样做的修改相当简单:

• 当您已经在 child 的子树中找到距离时，只需返回它即可。
• 如果您在不同的 child 的子树中找到了 A 和 B，则返回 A 和 B 之间的距离。
• 如果您只在 child 的子树中找到了 A 或 B，只需返回到 A 或 B 的距离，并带有一个指示器来说明您要返回的内容。