找到給定的兩個節點的共同祖先的算法

Question

如果兩個節點和樹的根都給我。如何找到兩個節點的共同祖先？

Answer 1

你可以按照這個方法

雖然從上遍歷二叉搜索樹底部的節點n我們與N1和N2之間，即價值遭遇，N1 <ñ< N2是最低或最小公共祖先（LCA）n1和n2（其中n1 < n2）。因此，只需按照預定順序遍歷BST，如果找到值介於n1和n2之間的節點，那麼n是LCA，如果它的值大於n1和n2，則我們的LCA位於節點的左側，if它的價值比n1和n2都小，然後LCA位於右側。

其在面試中常見的編程問題，你可以很容易地找到了自己的解決方案上interview sites

Answer 2

你好這裏是一個Python實現，我發現有用的LCA： -

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)