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

给出一个根节点（到井形成二叉树）和其他两个节点（这是保证在树上，并且也不同），返回两个节点的最低共同祖先。

我不知道任何最不常见的祖先算法，所以我试图在现场制作一个。我公司生产的以下代码：

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的情况 - 我错过了什么？

来源

2014-12-07 Patrick Collins

现在让'b'成为'a'的子节点，反之亦然。 – 2014-12-07 10:43:43

@MartijnPieters啊，谢谢，就是这样。如果你能够做出答案，我很乐意接受。否则，也许我应该删除这个问题？ – 2014-12-07 10:46:05

你似乎认为a和b在它们的lca的不同子树中。这不是一个好的假设。从边界案例开始。 'a是b'，'a是根'，树只剩下分支等。你会感到惊讶。 – 2014-12-07 10:51:00

你忘了说明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-07 10:51:30

树不能保证排序或有键。我不相信“二叉树”意味着“二叉搜索树”。 – 2014-12-07 11:02:56

@PatrickCollins：对，这是一个重要的区别。你允许用深度注释节点吗？ – 2014-12-07 11:05:33

写在最上面的问题是我得到的完整提示。我后来给出了一个答案，即面试官认为是正确的，包括建立从根到'a'的路径，并从根到'b'，然后检查该路径的交集。 – 2014-12-07 11:06:55

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

看看这个简单的反例：

a 
    b None

a也给出root，并调用该函数时，可以调用check_subtree(root)，这是a，那么你会发现，这是你在找什么for（在返回1的停止子句中），并且在没有设置lca的情况下自动返回1。

来源

2014-12-07 10:47:31 amit

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

回答

相关问题