LeetCode 經典題解：二叉樹的最小深度（遞迴與迭代法）

LeetCode 111：二叉樹的最小深度 —— 遞迴解法深度解析

題目描述

給定一棵二叉樹，找出其最小深度。最小深度是從根節點到最近葉子節點的最短路徑上的節點數。

關鍵點：葉子節點是指沒有子節點的節點。若根節點只有一個子樹，最小深度不應為 1，而應沿著該子樹繼續尋找葉子。

遞迴解法

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == NULL) return 0;
        
        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);
        
        // 關鍵邏輯：處理單邊子樹情況
        if (leftDepth == 0 && rightDepth == 0) 
            return 1;                    // 葉子節點
        if (leftDepth == 0 || rightDepth == 0) 
            return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;  // 單邊子樹
        if (leftDepth != 0 && rightDepth != 0) 
            return leftDepth > rightDepth ? rightDepth + 1 : leftDepth + 1;  // 雙邊子樹取較小
    }
};

核心邏輯圖解

常見錯誤警示

錯誤寫法：return min(leftDepth, rightDepth) + 1;

反例：根節點只有左子樹，左子樹深度為 3。錯誤寫法返回 min(3, 0) + 1 = 1，但正確答案應為 4（根→左→左→葉子）。

原因：min(3, 0) 取到了空子樹的深度 0，實際上空子樹不包含葉子節點，不能作為路徑終點。

迭代法（BFS 層序遍歷）

層序遍歷第一個遇到的葉子節點所在層數即為最小深度，通常比遞迴更快（可提前終止）。

int minDepth(TreeNode* root) {
    if (!root) return 0;
    queue q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        depth++;
        int sz = q.size();
        for (int i = 0; i < sz; ++i) {
            TreeNode* node = q.front(); q.pop();
            if (!node->left && !node->right) return depth;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return depth;
}

複雜度分析

• 遞迴：時間 O(N)，空間 O(H)（H 為樹高，最壞 O(N)）
• BFS：時間 O(N)，空間 O(W)（W 為最大層寬度）

核心收穫

1. 最小深度 ≠ 最大深度的對稱，**單邊子樹處理是關鍵**
2. 遞迴需顯式判斷子樹是否為空，不能直接用 min
3. BFS 天然適合「最近/最短」類問題，可提前剪枝