Как повысить эффективность определения того, является ли дерево AVL-деревом в python?

Question

В моем следующем коде есть два рекурсивных слоя. Мне было интересно, возможно ли «объединить» два в том смысле, что код более эффективен?

class Solution(object): 
    def maxDepth(self, root): 
     if root == None: 
      return 0 
     return max(self.maxDepth(root.left), self.maxDepth(root.right))+1 

    def isBalanced(self, root): 

     if root == None: 
      return True 
     if abs(self.maxDepth(root.left) - self.maxDepth(root.right)) <= 1: 
      return self.isBalanced(root.left) and self.isBalanced(root.right) 
     return False 

Answer 1

Чтобы определить функцию, которая проверяет, является ли дерево отлично сбалансировано или нет, вы можете посетить только один раз в дерево с помощью алгоритма, приведенного в следующем псевдокоде (я не знаю достаточно синтаксиса Python, чтобы написать явный код):

isBalanced(tree): 
    if tree is null 
    then return the tuple (true, 0) 
    else be (bal1, lev1) the result of calling isBalanced on the left child of tree 
    and be (bal2, lev2) the result of calling isBalanced on the rigth child of tree 
    if (bal1 is false) or (bal2 is false) 
    then exit from the function with the tuple (false, 0) 
    else if lev1 = lev2 
      then return the tuple (true, 1+lev1) 
      else exit from the function with the tuple (false, 0) 

в основном алгоритм посещает дерево вычисления рекурсивно, если поддерево является сбалансированным, или нет, и, в случае, если сбалансировано, глубина дерева.

Команда «выход из функции» должна вызывать немедленный выход из всех рекурсивных вызовов функции, если это возможно в Python, иначе это просто возврат из текущего вызова с указанным кортежем.

Конечно, в конце функции полезен только первый компонент кортежа (информация о сбалансированности).

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

Answer 2

Вот перевод Python из Renzo's pseudocode:

class Tree: 
    def __init__(self, left=None, right=None): 
     self.left = left 
     self.right = right 


def isBalanced(tree): 
    exitValue = None 

    def isBalancedCore(tree): 
     nonlocal exitValue 
     if exitValue is not None: 
      return exitValue 

     if tree is None: 
      return (True, 0) 
     else: 
      bal1, lev1 = isBalancedCore(tree.left) 
      bal2, lev2 = isBalancedCore(tree.right) 
      if not bal1 or not bal2: 
       exitValue = (False, 0) 
       return exitValue 
      elif lev1 == lev2: 
       return (True, lev1+1) 
      else: 
       exitValue = (False, 0) 
       return exitValue 

    return isBalancedCore(tree)[0]