LeetCode 二叉樹最小深度：BFS 層序遍歷最優解法

題目描述

求二叉樹的最小深度：從根節點到最近葉子節點的路徑節點數。注意：葉子節點定義為左右子節點均為空。

示例：
3
/ \
9 20
/ \
15 7
/
14
最小深度 = 2（路徑 3→9）。

為什麼選 BFS？

BFS 逐層遍歷，首次遇到葉子節點即為最小深度，可提前終止。DFS 需遍歷全樹才能確定最小值，效率較低。

算法步驟

1. 根為空返回 0。
2. 隊列初始化放入根節點，depth = 0。
3. 循環處理每一層：
   depth++
   遍歷當前層所有節點：
     若無左右子節點 → 返回 depth（找到最淺葉子）
     非空子節點入隊下一層

Python 參考實現

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        depth = 0
        curr_level = [root]
        while curr_level:
            depth += 1
            next_level = []
            for node in curr_level:
                if not node.left and not node.right:
                    return depth
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            curr_level = next_level
        return depth

C++ 版本

int minDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        ++depth;
        int sz = q.size();
        for (int i = 0; i < sz; ++i) {
            auto 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(w)：w 為樹最大寬度，最壞 O(n)。

常見陷阱

❌ 錯誤寫法：return min(minDepth(left), minDepth(right)) + 1
此法在單子樹情況下會錯誤返回 1（應為子樹深度+1）。BFS 天然規避此問題。