comment améliorer l'efficacité pour déterminer si un arbre est un arbre AVL en python?

Question

Actuellement, il y a deux couches récursives dans mon code suivant. Je me demandais s'il était possible de «fusionner» les deux en ce sens que le code est plus efficace?

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

Pour définir une fonction qui vérifie si un arbre est parfaitement équilibré ou non, vous pouvez visiter qu'une seule fois l'arbre avec un algorithme donné dans le pseudo-code suivant (je ne connais pas assez la syntaxe de Python pour écrire un code explicite):

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) 

Fondamentalement, l'algorithme rend visite l'arbre calcul récursive si un sous-arbre est équilibré ou non, et, au cas où il est équilibré, la profondeur de l'arbre. La commande "quitter la fonction" devrait provoquer la sortie immédiate de tous les appels récursifs de la fonction, si cela est possible en Python, sinon c'est simplement un retour de l'appel en cours avec le n-uplet spécifié.

Bien entendu, à la fin de la fonction, seul le premier composant du tuple (l'information sur l'équilibre) est utile.

Si vous voulez vérifier si un arbre est équilibré avec au plus une différence de 1 sur la profondeur des feuilles, vous pouvez étendre cette solution en retournant un tuple à trois éléments (équilibré, profondeur minimale, profondeur maximale), et vérifier dans le cas général si les profondeurs (minimum et maximum) des enfants sont cohérentes (et ensuite retourner le minimum et le maximum actuels).

Answer 2

Voici une traduction Python de 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]