从两个目标节点开始遍历祖先树时，我可以标记我在递归调用中看到的节点以找到它们的最低共同祖先吗？

Question

我正在解决一个问题，其中给定一个 tree，其 root 和 two target nodes（descendantOne 和 descendantTwo）在树.

我被要求return两个目标节点的lowest common ancestor。

然而，我们也被告知我们的树是 AncestralTree 的一个实例，它由以下公式给出：

class AncestralTree:
    def __init__(self, name):
        self.name = name
        self.ancestor = None

即对于树中的每个节点，我们只有向上指向父节点的指针（与具有从父节点到子节点的指针的普通树相反！）

我解决这个问题的思路是从两个目标节点开始向上移动，标记我们访问的每个节点。有一次，我们必然会访问一个节点两次，而第一次是——这是我们最低的共同祖先！

这是我的代码：

def getYoungestCommonAncestor(topAncestor, descendantOne, descendantTwo):
    lowestCommonAncestor = None
    
    def checkAncestors(topAncestor,descendantOne, descendantTwo,descendantOneSeen,descendantTwoSeen): 
        if descendantOneSeen and descendantTwoSeen: 
            return descendantOne
        else: 
            return None
        
    while not lowestCommonAncestor:
        **lowestCommonAncestor = checkAncestors(topAncestor,descendantOne.ancestor, descendantTwo,True,False)
        if lowestCommonAncestor: 
            break
        **lowestCommonAncestor = checkAncestors(topAncestor,descendantOne, descendantTwo.ancestor,False,True)
        if descendantOne.ancestor == topAncestor: 
            pass 
        else: 
            descendantOne = descendantOne.ancestor 
        if descendantTwo.ancestor == topAncestor: 
            pass
        else:
            descendantTwo= descendantTwo.ancestor
        
    return lowestCommonAncestor

我在代码中的两个 recursion calls 旁边放了星号 **，因为我认为这是问题所在。

因为我运行递归调用，例如假设我们已经看到 descendantOne，当我运行对 descendantTwo 的递归调用时，它会自动将 descendantOneSeen 标记为 false 在它的递归调用中。所以这导致我们永远不会有 descendantOneSeen 和 descendantTwoSeen 为真。

当我运行上面的代码时，我确实遇到了一个无限循环错误 - 我明白为什么了。

有没有什么方法可以修改我的代码以在不使用 global variables 的情况下实现我想要的？

Answer 1

事实上，它不会像那样工作，因为 descendantOneSeen and descendantTwoSeen 永远不会是真的。但是，即使您修复了这部分逻辑，两个节点与其最低共同祖先之间的距离也可能相距甚远……因此您需要不同的算法。

一种方法是像您一样一前一后走到树的顶部，但是当您到达顶部时，继续在 other 起始节点处引用该引用。当两个引用都向下跳转时，它们在共同的最低祖先相遇时将访问完全相同数量的节点。

这导致一个非常简单的算法：

def getYoungestCommonAncestor(topAncestor, descendantOne, descendantTwo):
    nodeOne = descendantOne
    nodeTwo = descendantTwo
    while nodeOne is not nodeTwo:
        nodeOne = descendantTwo if nodeOne is topAncestor else nodeOne.ancestor
        nodeTwo = descendantOne if nodeTwo is topAncestor else nodeTwo.ancestor 
    return nodeOne

这可能看起来很狡猾，因为这些节点引用永远相等看起来像是运气问题。但是 nodeOne 和 nodeTwo 引用都将从两个起点（descendantOne 和 descendantTwo）开始——这只是它们执行此操作的顺序颠倒了。但这仍然意味着他们将在访问共同祖先时访问相同数量的节点 second 时间。

这是您的示例图，其中两个起始节点是 C 和 I。我已经删除了一些节点，因为它们无法从这两个节点访问，所以它们不起作用：

所以我们的想法是我们从节点 I 和 C 开始遍历。通过应用当遍历到达根时将从 other 起始节点继续的规则，我们看到从 I 我们将首先跟随红色边缘，然后是绿色边缘，而从 C 开始的路径将首先沿着绿色边缘，然后沿着绿色边缘。

由此可见，这两次遍历访问绿色和红色边缘所需的步数相同（只是顺序不同），因此它们将到达节点 A 在他们各自访问它秒时间的同时。

从两个目标节点开始遍历祖先树时，我可以标记我在递归调用中看到的节点以找到它们的最低共同祖先吗？

While traversing an ancestor tree starting from two target nodes, can I mark nodes I've seen in recursive calls to find their lowest common ancestor?

python

tree