Вычислить максимальную разницу между узлами в двоичном дереве

Question

Есть ли способ вычислить максимальную разницу между значениями узлов без сохранения в списке? Я надеялся сделать это за 1 проход, но это не представляется возможным. Это было связано с вопросом собеседований для вычисления амплитуды двоичного дерева, определяемого как максимальная абсолютная разница узлов.

 def max_diff(nodes): 
      return abs(max(nodes) - min(nodes)) 

     def amplitude(T): 
      nodes = [] 
      def calc_amplitude(T, nodes): 

       if not isinstance(T, tuple): 
        if not isinstance(T, int): 
         return 0 
        nodes.append(T) 
        return T 
       else: 
        [calc_amplitude(t, nodes) for t in T] 
        return max_diff(nodes) 
      return calc_amplitude(T, nodes) 

     tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None))) 

     print amplitude(tree) 

Answer 1

В случае, если вы хотите узнать максимальную разницу между двумя узлами на любом пути от корня до листа вы можете использовать следующий код:

def amplitude(tree, cur_min=None, cur_max=None): 
    if tree is None: 
     if cur_min is None: 
      return 0 
     else: 
      return cur_max - cur_min 

    if cur_min is None: 
     cur_min = cur_max = tree[0] 
    else: 
     cur_min = min(cur_min, tree[0]) 
     cur_max = max(cur_max, tree[0]) 

    return max(amplitude(tree[1], cur_min, cur_max), 
       amplitude(tree[2], cur_min, cur_max)) 

Она будет отслеживать минимальное и максимальное значение на каждом пути , Как только он достигнет листа, он просто вернет разницу между этими двумя, тем самым прекратив рекурсию. Для нелистовых узлов сначала будет обновлено минимальное и максимальное значение. Затем он повторяет оба дочерних элемента и возвращает максимальное значение между двумя результатами.