python - python中如何提高判断一棵树是否为AVL树的效率？

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，您可以通过返回具有三个元素(平衡、最小深度、最大深度)的元组来扩展此解决方案，并且在一般情况下检查子级的深度(最小值和最大值)是否一致(然后返回当前的最小值和最大值)。