Алгоритм поиска общего предка двух узлов, заданных

Question

Если мне нужны два узла и корень дерева. Как найти общий предк двух узлов?

Answer 1

Вы можете следовать этому подходу

при обходе двоичного дерева поиска сверху вниз, первый узле п мы сталкиваемся со значением между n1 и n2, т.е. n1 < п < n2 является низким или Наименее распространенный предок (LCA) n1 и n2 (где n1 < n2). Поэтому просто переходите BST в предварительном порядке, если вы найдете узел со значением между n1 и n2, тогда n - это LCA, если это значение больше, чем n1 и n2, тогда наша LCA лежит на левой стороне узла, если это значение меньше, чем 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)