题解 | #判断是不是平衡二叉树#

先审好题，要求满足两个条件：

1. 左右两个子树的深度差不超过1
2. 左右两个子树本身也是平衡二叉树

功能分解：

1. 求一个二叉树的深度
2. 判断是否为平衡二叉树，包括其左右子树是否也是平衡二叉树

可通过两个递归函数实现

class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot:
            return True
        left = self.deep(pRoot.left)
        right = self.deep(pRoot.right)
        # 满足左右子树的深度差值不超过1
        if abs(left - right) > 1:
            return False
        #　左右子树本身也是平衡的
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
    
    # 求树的高度
    def deep(self, root: TreeNode) -> bool:
        if not root:
            return 0
        left = self.deep(root.left)
        right = self.deep(root.right)
        return left + 1  if left > right else right + 1