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(n2)
• 空間復雜度：O(h)（遞歸?？臻g，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問題

七、總結

進階思考：如何用迭代法實現？可以參考后序遍歷的棧實現方式，但遞歸方案在本題中更為簡潔。

”`