LeetCode如何检查二叉树的平衡性

# LeetCode如何检查二叉树的平衡性

## 引言

在算法面试和编程竞赛中，二叉树是高频考点之一。其中，**平衡二叉树的判断**更是经典问题，LeetCode上对应题目为[110. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)。本文将深入探讨该问题的解决方案，包括暴力解法、优化解法以及相关的时间复杂度分析。

---

## 一、问题定义

### 平衡二叉树的性质
根据题目要求，平衡二叉树定义为：
> 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1，并且左右子树本身也必须是平衡二叉树。

### 示例
```python
# 平衡二叉树示例
    3
   / \
  9  20
    /  \
   15   7

# 非平衡二叉树示例
    1
   / \
  2   2
 / \
3   3
/ \
4   4

二、暴力解法（自顶向下递归）

算法思路

1. 对于当前节点，计算左右子树的高度
2. 检查高度差是否 ≤1
3. 递归检查左右子树是否平衡

代码实现

def isBalanced(root):
    def height(node):
        if not node:
            return 0
        return max(height(node.left), height(node.right)) + 1
    
    if not root:
        return True
    left_height = height(root.left)
    right_height = height(root.right)
    return abs(left_height - right_height) <= 1 and \
           isBalanced(root.left) and \
           isBalanced(root.right)

时间复杂度分析

• 计算高度：O(n)
• 递归调用：O(log n)~O(n)次（取决于树结构）
• 最坏情况（链式树）：O(n²)
• 空间复杂度：O(h)（递归栈空间，h为树高）

三、优化解法（自底向上递归）

算法改进点

暴力解法存在重复计算子树高度的问题。优化思路： 1. 在计算高度的同时判断平衡性 2. 若子树不平衡，直接返回-1标记失败

代码实现

def isBalanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        right = check(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return max(left, right) + 1
    
    return check(root) != -1

时间复杂度分析

• 每个节点仅访问一次：O(n)
• 空间复杂度：O(h)

执行过程示例

       [3]
      /   \
    [9]   [20]
          /  \
        [15] [7]

计算顺序：
1. 9 → 高度1（左右子树高度0）
2. 15 → 高度1
3. 7 → 高度1
4. 20 → max(1,1)+1=2
5. 3 → max(1,2)+1=3
无返回-1的情况 → 平衡

四、对比测试

测试用例设计

两种解法性能对比

五、边界情况处理

常见陷阱

1. None节点处理：必须返回高度0
2. 提前终止条件：当子树返回-1时应立即终止计算
3. 浮点数精度：某些语言中abs()函数需要整数输入

错误代码示例

# 错误：未处理子树不平衡的传递
def check(node):
    if not node:
        return 0
    left = check(node.left)
    right = check(node.right)
    return abs(left - right) <= 1  # 错误！只比较了当前节点

六、相关题目拓展

1. 104. Maximum Depth of Binary Tree
   • 基础的高度计算练习
2. 543. Diameter of Binary Tree
   • 类似的高度差应用
3. 124. Binary Tree Maximum Path Sum
   • 更复杂的树形DP问题

七、总结

进阶思考：如何用迭代法实现？可以参考后序遍历的栈实现方式，但递归方案在本题中更为简洁。

”`