3

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

  1. 让每个节点包含其基数列表，并执行连接，找到最长的公共前缀，然后取最后一个元素。不幸的是，我不知道有任何内置方法可以做最长的公共前缀，所以这需要手动循环。

  2. 让每个节点包含一组它的基并执行一组交集，并取最大元素。但这需要定义自定义比较运算符，我什至不确定它是否会起作用。

我该怎么办？我正在寻找有利于简单而不是性能的东西，因此需要复杂处理的解决方案已经出现。

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

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

6 回答 6

6

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

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

于 2012-08-10T17:22:32.757 回答
5

取每个节点的深度（到根的距离）。如果一个比另一个低，则从较低的节点向上走，直到深度相等。然后检查身份，每次检查失败时在每一侧向上移动。

您可以使用单个 while 循环来执行此操作。一旦您选择了具有相同深度的祖先：

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

当 while 循环终止时，ancestorA每个ancestorB人都将成为您的共同祖先。

这不仅应该非常简单，而且应该相当快。

于 2012-08-10T17:03:33.410 回答
2

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的祖先集来潜在地加速该过程（最终以空间占用为代价）——一旦找到公共节点就停止 a。代码有点做作，因为您必须处理其中一个分支在另一个之前到达根：

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* !!!
于 2016-03-10T21:35:22.380 回答
0

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

于 2012-08-10T17:47:10.693 回答
0

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

于 2012-08-10T22:02:48.683 回答
0

既然在这两种情况下你已经有一个指向父节点的指针，为什么不这样做：（类似于奇怪的加拿大所说的，但是......）

创建每个节点的父节点的列表，在每个阶段按顺序构建列表。所以随着你走得更高list_a而增长。list_b将每个列表中添加的最后一项与其他项进行比较。只要 list_a 中的某个项目与 list_b 中的某个项目匹配，您就有了最低的共同祖先。

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

您不需要一直重建链直到根。在任何情况下，您都必须按顺序（向前或向后）检查每个父级。

于 2012-08-11T07:33:47.183 回答