这个最小共同祖先算法有什么问题？

Question

在一次求职面试中，我被问到以下问题：

Given a root node (to a well formed binary tree) and two other nodes (which are guaranteed to be in the tree, and are also distinct), return the lowest common ancestor of the two nodes.

我不知道任何最不常见的祖先算法，所以我试着当场制作一个。我产生了以下代码：

def least_common_ancestor(root, a, b):
    lca = [None]
    def check_subtree(subtree, lca=lca):
        if lca[0] is not None or subtree is None:
            return 0

        if subtree is a or subtree is b:
            return 1
        else:
            ans = sum(check_subtree(n) for n in (subtree.left, subtree.right))

        if ans == 2:
            lca[0] = subtree
            return 0

        return ans

    check_subtree(root)

    return lca[0]


class Node:
    def __init__(self, left, right):
        self.left = left
        self.right = right

我尝试了以下测试用例，得到了我期望的答案：

^{pr2}$

但我的面试官告诉我，“有一类树，你的算法没有返回任何结果。”我搞不清是什么，于是我把面试搞砸了。我想不出这样一种情况：算法会在不ans变成2的情况下到达树的底部——我遗漏了什么？在

Answer 1

缺少a是b的祖先的情况。在

看看这个简单的反例：

    a
  b  None

a也被赋予root，当调用函数时，您调用check_subtree(root)，它是a，然后您发现这就是您要查找的（在返回1的stop子句中），并立即返回1，而不按本应设置lca。在

Answer 2

您忘了说明a是b的直系祖先，反之亦然。一旦找到其中一个节点就停止搜索并返回1，因此在这种情况下，您永远找不到另一个节点。在

你得到了一个格式良好的二叉搜索树；这种树的一个特性是，你可以根据元素相对于当前节点的相对大小轻松地找到元素；较小的元素进入左边的子树，较大的元素进入右边的子树。因此，如果您知道两个元素都在树中，则只需比较键；一旦您发现位于两个目标节点之间的节点，或等于它们的一个节点，您就找到了最低的共同祖先。在

示例节点从未包含存储在树中的键，因此无法使用此属性，但如果确实包含，则应使用：

def lca(tree, a, b):
    if a.key <= tree.key <= b.key:
        return tree
    if a.key < tree.key and b.key < tree.key:
        return lca(tree.left, a, b)
    return lca(tree.right, a, b)

如果树仅仅是一个“常规”二叉树，而不是搜索树，那么您唯一的选择就是找到这两个元素的路径并找到这些路径发散的点。在

如果您的二叉树维护父引用和depth，则可以有效地完成此操作；只需从两个节点中的较深位置向上走，直到您找到一个公共节点；这是最不常见的祖先节点。在

如果没有这两个元素，则必须从根开始，通过单独的搜索找到两个节点的路径，然后在这两个路径中找到最后一个公共节点。在