题目的主要信息：

• 判断给定的一棵树是否是平衡二叉树
• 平衡二叉树：：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

方法一：自顶向下求深度

具体做法：

递归遍历二叉树的每个结点，再递归计算每个结点的左右子树深度，判断每个结点的是否满足平衡二叉树的要求。

class Solution:
    def depth(self, root): #计算子树深度
        if root is None: #空结点没有深度
            return 0
        left = self.depth(root.left) #递归计算左右子树深度
        right = self.depth(root.right)
        return max(left, right) + 1 #左右子树最大深度+1
    def IsBalanced_Solution(self, pRoot):
        if pRoot is None: #空树是平衡的
            return True
        left = self.depth(pRoot.left) #计算左子树深度
        right = self.depth(pRoot.right)#计算右子树深度
        if abs(left - right) > 1: #深度差不能超过1
            return False
        #判断子树是否平衡
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，需要遍历二叉树的每个结点，共$O(n)O(n)$，然后对于每个结点我们要计算其左右子树的深度，最大深度不超过$O(lo{g}_{2}n)O(log\_2n)$，如果超过了则不是平衡二叉树，中间就可以结束函数
• 空间复杂度：$O(n)O(n)$，递归栈需要的空间

方法二：自底向上判断

具体做法：

自底向上递归的方法类似于后序遍历，对于当前遍历到的节点，优先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

class Solution:
    def IsBalanced_Solution(self, pRoot):
        def recur(pRoot):
            if pRoot is None: #空树没有深度
                return 0;
            left = recur(pRoot.left) #计算左子树深度
            if left == - 1: 
                return - 1
            right = recur(pRoot.right) #计算右子树深度
            if right == -1:
                return -1
            return max(left, right) + 1 if abs(left - right) <= 1 else -1
        return recur(pRoot) != -1 #-1表示深度差大于等于2

复杂度分析：

• 时间复杂度：$O(n)O(n)$，后序遍历每个结点
• 空间复杂度：$O(n)O(n)$，递归栈最大深度