2

在一次工作面试中，我被问到以下问题：

给定一个根节点（到一个结构良好的二叉树）和两个其他节点（保证在树中，并且也是不同的），返回两个节点的最低共同祖先。

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

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。” 我不知道那是什么，我把面试搞砸了。我想不出算法会在不ans变成 2 的情况下到达树底部的情况——我错过了什么？

4

2 回答 2

3

您忘记考虑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)

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

如果您的二叉树维护父引用和深度，则可以有效地完成；只需向上走两个节点中较深的一个，直到您处于相同的深度，然后从两个节点继续向上，直到找到一个公共节点；那是最不常见的祖先。

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

于 2014-12-07T10:51:30.553 回答
1

您错过a了b.

看一个简单的反例：

    a
  b  None

a也给出为root，并且在调用函数时，调用check_subtree(root)，即a，然后您会发现这是您要查找的内容（在返回 1 的停止子句中），并立即返回1而无需进行lca应有的设置。

于 2014-12-07T10:47:31.607 回答