data-structures - 给定两个节点的共同祖先的算法

Question

如果给我两个节点和树的根。如何找到两个节点的共同祖先？

Answer 1

您可以按照这种方法

从上到下遍历二叉搜索树，我们遇到的第一个节点 n 的值介于 n1 和 n2 之间，即 n1 < n < n2 是 n1 和 n2 的最低或最小公共祖先（LCA）（其中 n1 < n2)。所以只需按顺序遍历 BST，如果你找到一个值在 n1 和 n2 之间的节点，那么 n 就是 LCA，如果它的值大于 n1 和 n2，那么我们的 LCA 位于节点的左侧，如果它的值小于 n1 和 n2，则 LCA 位于右侧。

这是面试中常见的编程问题，您可以在面试网站上轻松找到它的解决方案

Answer 2

嗨，这是一个我发现对 LCA 有用的 python 实现：-

class BST(object):
def __init__(self, val=None, right=None, left=None):
    self.val = val
    self.right = right
    self.left = left
    return None

def __nonzero__(self):
    return self.val is not None

def insert(self, item):
    if not self:
        self.val = item
    elif item < self.val:
        if self.left:
            return self.left.insert(item)
        else:
            self.left = BST(val=item)
    elif item > self.val:
        if self.right:
            return self.right.insert(item)
        else:
            self.right = BST(val=item)
    return None

def lca(self, m, n):
    if n < self.val:
        return self.left.lca(m, n)
    elif m > self.val:
        return self.right.lca(m, n)
    else:
        return self.val


if __name__ == "__main__":
b = BST()
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    b.insert(k)
for pair in [(4, 7), (4, 10), (1, 4), (1, 3), (3, 6)]:
    print b.lca(*pair)