平衡二叉树-LeetCode

110. 平衡二叉树 - Balanced Binary Tree

🎯 问题描述（来源于LeetCode）

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

说明：

• 空树被认为是平衡二叉树。
• 树的高度是指从根节点到最远叶子节点的最长路径上的节点数（通常以边的数量计算，本题以节点数量计算）。

示例：

• 示例 1：

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

• 示例 2：

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

💻 解题思路

思路1：后序遍历 + 提前剪枝（自底向上）

算法步骤

1. 定义递归函数 get_h(node)：

   • 返回以 node 为根的树的高度，如果该子树不平衡则返回 -1。

2. 递归终止条件：

   • 如果 node 为 None，返回高度 0。

3. 递归计算左子树高度：

   • 调用 get_h(node.left)，如果返回 -1（左子树不平衡），则直接返回 -1，不再继续。

4. 递归计算右子树高度：

   • 调用 get_h(node.right)，如果返回 -1 或者左右子树高度差绝对值大于 1，则返回 -1。

5. 计算当前节点的高度：

   • 如果左右子树均平衡，当前节点的高度为 max(左高, 右高) + 1。

6. 最终判断：

   • 调用 get_h(root)，若其不等于 -1 则二叉树平衡，否则不平衡。

思路1：代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_h(node):
            if node is None:
                return 0
            l_hight = get_h(node.left)
            if l_hight == -1:
                return -1
            r_hight = get_h(node.right)
            if r_hight == -1 or abs(l_hight - r_hight) > 1:
                return -1
            return max(l_hight, r_hight) + 1
        return get_h(root) != -1

思路1：📊 性能分析

复杂度验证

• 时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点数。每个节点最多被访问一次（遇到不平衡立即返回）。
• 空间复杂度：$O(h)$，其中 $h$ 为树的高度。递归调用栈的深度等于树高，最坏情况（链状树）为 $O(n)$。

思考

• 本题常见的暴力解法是先计算左右子树高度再递归判断，时间复杂度为 $O(n^2)$。而本题的后序遍历 + 剪枝方法将复杂度降为 $O(n)$，是更优的实现。
• 注意递归时先判断左子树是否平衡，再判断右子树，利用 -1 作为不平衡标志，避免了重复计算高度。
• 也可以使用迭代 + 后序遍历（显式栈）实现，但递归写法最简洁清晰。