Python的最近公共祖先

Question

什么是在Python中实现最近公共祖先的最简单方法？我有一棵树，每个节点都有一个指向其父节点的指针，并且我想能够找到给定两个节点的第一个公共祖先。我想出了几个想法，但没有一个特别吸引人。

1. 让每个节点包含其基础列表，并执行连接操作，查找最长公共前缀，然后取最后一个元素。不幸的是，我不知道任何内置的方法来执行最长公共前缀，因此这需要手动循环。
2. 让每个节点包含其基础集合并执行集合交集，并取最大元素。但这需要定义自定义比较运算符，我甚至不确定它是否会起作用。

我该怎么办？我正在寻找偏向简单而非性能的解决方案，因此需要复杂处理的解决方案不适用。

编辑：我发现虽然没有内置方法，但您可以使用zip在一行中执行最长公共前缀，因此它仍然相当简单。

common = [x for x in zip(*baselists) if len(set(x)) == 1][-1]

- Antimony

Answer 1

假设您无法修改树来包含深度，您可以执行以下操作:

对于每个节点，递归向上遍历树，直到到达根。在每个父节点处，将节点插入列表中。这应该为您提供list_a和list_b。迭代最短的列表，比较每个列表的元素。当您找到不匹配的元素时，前一个条目是您的最大父元素。

- aaronlevin

---

如果需要的话，您可以在不修改树本身的情况下计算深度。只需使用递归函数或迭代节点的祖先即可。 - Justin Blank

Answer 2

计算每个节点的深度（从根节点开始的距离）。如果一个节点比另一个节点低，就从较低的节点往上遍历树，直到它们的深度相等。然后检查它们是否相同，每次检查失败时在每一侧将其向上移动。

你可以通过一个while循环来完成这个过程。一旦选择了深度相等的节点：

while (ancestorA !== ancestorB) {
    ancestorA = ancestorA.parent();
    ancestorB = ancestorB.parent();
}

当 while 循环终止时，ancestorA 和 ancestorB 分别是您的共同祖先。 这不仅应该相当简单，而且也相当快。

- Justin Blank

---

有没有办法修改这个程序，使其不需要两个循环？ - Antimony

如果您无法获得深度呢？上面的算法将毫无帮助。然而，维护一个父节点列表，并在每一步比较其与另一个节点的祖先，即使深度未存储在树中，也可以得到结果。尽管如此，这需要反复循环遍历祖先列表，可能会减慢速度。 - aneroid

你可以编写一个简单的函数，通过递归或迭代祖先节点来获取深度。在节点/树上定义该方法只是面向对象设计的一种便利性/特性。 - Justin Blank

在这种情况下，为了结合我们的答案以及@weirdcanada的答案：在获取两个节点的深度（假设它没有存储在类/对象中）的同时，构建父节点列表。然后使用结果较低的深度（<-更高/更少的节点到根），例如n，仅保留较长列表的前n + 1项[:n+1]。然后像上面那样进行比较。从尾部开始与根端进行检查基于分歧快/慢不同。但是，从尾部开始意味着第一个匹配是正确的，您不需要向后走一步（“上一个条目”），就像wc的解决方案一样。 - aneroid

Answer 3

Python内置集合类型。那么为什么不使用类似以下伪代码的东西：

a_ancestors = set()
while a:
  a_ancestors.add(a)
  a = a.parent

while b:
  if b in a_ancestors:
    return b
  b = b.parent

return None # <- can't reach that for a *tree* !!!

这将构建节点a（包括a本身）的所有祖先的（无序）集合。

然后，我们循环遍历b的所有祖先。根据定义，是第一个是a的祖先的b的祖先将是第一个共同的祖先。这在空间和时间上都是O(n)复杂度。

---

你可以通过同时收集a和b的祖先集合来加快这个过程（可能会牺牲空间占用）。代码有点矫揉造作，因为你必须处理其中一个分支在另一个分支之前到达根节点的情况：

visited = set()
while a or b:
  if a:
    if a in visited:
      return a
    visited.add(a)
    a = a.parent

  if b:
    if b in visited:
      return b
    visited.add(b)
    b = b.parent

return None # <- can't reach that for a *tree* !!!

- Sylvain Leroux

Answer 4

既然在这两种情况下您已经有了指向父节点的指针，为什么不这样做：

创建每个节点的父节点列表，在每个阶段顺序构建列表。因此，list_a和list_b随着您向上移动而增长。将每个列表最后添加的项与另一个列表的项进行比较。一旦list_a中的项与list_b中的某个项匹配，您就找到了最低公共祖先。

while (parent_a not in list_b) or (parent_b not in list_a):
    ...

你不需要一直重建链直到根节点。无论如何，你都必须按顺序检查每个父节点（向前或向后）。

- aneroid

---

这是一个O(n^2)算法。我知道原帖作者说他想要简单性高于性能，但如果树足够高，这个算法的性能会非常糟糕。 - Justin Blank

Answer 5

我想这取决于你的树以及它将包含多少对象。如果内存使用量合理（可能少于几百万个节点，但这只是我的猜测），我会使用您的建议＃2。在集合中，只需保留每个基数的字符串表示形式，因此内置比较将起作用。应该非常快，并且我想您可以仅使用几行代码实现它。如果字符串表示不实用，或者如果您需要对象本身并且无法实现所有对象的主字典，则只需在节点对象中定义比较方法（eq和neq，如果我没记错的话）。

- DaveTheScientist

Answer 6

维护父节点集合的想法，最好使用带有 = 的哈希映射，因为在这种情况下，您不需要在父节点列表中搜索 logn。因此，在每次迭代中检查此映射，如果当前节点的父节点已经存在于映射中，则该父节点是您的结果。在最坏的情况下，它给出 O(n)，但如果您同时开始分析两个节点，则在某些情况下，您将能够更快地找到它。

- Rrr