平衡二叉树

概述：给定一个二叉树，判断它是否是高度平衡的二叉树。一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

输入：root = [3,9,20,null,null,15,7]
输出：true

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

输入：root = []
输出：true

方法一：自顶向下的递归

思路：定义函数 height，用于计算二叉树中的任意一个节点 p 的高度。对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1 ，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。

# 自顶向下的递归
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(root: TreeNode) -> int:
            if not root:
                return 0
            return max(height(root.left), height(root.right)) + 1
        if not root:
            return True
        return abs(height(root.left) - height(root.right)) <= 1 \
        and self.isBalanced(root.left) and self.isBalanced(root.right)

方法二：自底向上的递归

思路：自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。

# 自底向上的递归
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(root: TreeNode) -> int:
            if not root:
                return 0
            left_height = height(root.left)
            right_height = height(root.right)
            if left_height == -1 or right_height == -1 \
            or abs(left_height - right_height) > 1:
                return -1
            else:
                return max(left_height, right_height) + 1
        return height(root) >= 0

总结

自底向上的递归就是及时止损，自顶向下的递归就是不管三七二十一先把所有的高度算一遍！