这种最不常见的祖先算法有什么问题？

Question

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

给定一个根节点(到格式良好的二叉树(和另外两个节点(保证在树中，并且也是不同的(，返回两个节点的最低共同祖先。

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

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

我

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

a = Node(None, None)
b = Node(None, None)
tree = Node(Node(Node(None, a), b), None)
tree2 = Node(a, Node(Node(None, None), b))
tree3 = Node(a, b)

但是我的面试官告诉我，"有一类树，你的算法返回None。我不知道那是什么，我把采访弄乱了。我想不出算法会在没有变成 2 的情况下到达树的底部ans——我错过了什么？

Answer 1

你忘了说明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)

如果树只是一个"常规"二叉树，而不是搜索树，你唯一的选择是找到两个元素的路径并找到这些路径的分叉点。

如果你的二叉树保持父引用和深度，这可以有效地完成;只需沿着两个节点的更深处走，直到你处于相同的深度，然后从两个节点继续向上，直到找到一个共同的节点;这是最小共同的祖先。

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

Answer 2

您错过了a是b祖先的情况。

看一个简单的反例：

    a
  b  None

a 也作为 root 给出，当调用函数时，你调用 check_subtree(root) ，这是a，然后你发现这就是你要找的(在返回 1 的 stop 子句中(，并立即返回1而不按原样设置lca。