EasyRating 1248
111. Minimum Depth of Binary Tree
treedepth-first-searchbreadth-first-searchbinary-tree
解題說明
Minimum Depth of Binary Tree
題目描述：給定一棵二元樹，求從根節點到最近葉節點的最短路徑長度（即最小深度）。葉節點定義為沒有任何子節點的節點。
解題思路：本題有一個常見陷阱：最小深度不能單純取 min(左子樹最小深度, 右子樹最小深度)。原因在於若某個節點只有一側子樹，另一側為 null，則 null 那側不算是葉節點路徑，不應被納入計算。
BFS 解法（推薦）：使用層序遍歷，第一個遇到的葉節點（左右子節點皆為 null）所在的層即為最小深度。BFS 天然保證最短路徑先被找到，一旦找到葉節點即可提前回傳。
遞迴 DFS 解法：
- 若根節點為 null，回傳 0。
- 若左子樹為 null，僅考慮右子樹：
1 + minDepth(right)。 - 若右子樹為 null，僅考慮左子樹：
1 + minDepth(left)。 - 若兩側子樹皆存在，取兩側最小值：
1 + min(minDepth(left), minDepth(right))。
此邏輯確保只有真正的葉節點路徑才會被計算。
C++ 解法
複雜度分析
時間複雜度：O(n) — BFS 解法在最壞情況（葉節點在最末層）需遍歷所有 n 個節點；最佳情況（根節點的子節點即為葉節點）僅需遍歷極少節點。遞迴 DFS 解法同樣為 O(n)。
空間複雜度：O(n) — BFS 佇列在最壞情況下（滿二元樹最底層）需儲存約 n/2 個節點。DFS 遞迴堆疊深度為 O(h)，h 為樹高，退化樹時為 O(n)。
虛擬碼
BFS approach:
1. If root is null, return 0.
2. Initialize queue with root; depth = 0.
3. While queue is not empty:
a. Increment depth by 1.
b. For each node in the current level:
- Dequeue node.
- If node has no children, return depth (first leaf found).
- Enqueue node.left if not null.
- Enqueue node.right if not null.
4. Return depth.
DFS approach:
1. If root is null, return 0.
2. If root.left is null, return 1 + minDepth(root.right).
3. If root.right is null, return 1 + minDepth(root.left).
4. Return 1 + min(minDepth(root.left), minDepth(root.right)).其他解法
方法一：遞迴 DFS（處理單側子樹的特殊情況）
- 遞迴計算每個節點的最小深度，關鍵在於當節點只有一側子樹時，強制沿有子樹的那側遞迴，避免把 null 側誤算為深度為 0 的葉節點路徑。實作簡潔，但對深度不平衡的樹（如退化鏈狀樹）遞迴深度為 O(n)，有堆疊溢出風險。
- 時間複雜度：O(n)，空間複雜度：O(h)（h 為樹高）
方法二：迭代 DFS（使用明確堆疊）
- 以明確的
stack替代遞迴，每個堆疊元素儲存節點與對應深度。每次彈出節點後，若為葉節點則與當前最小值比較並更新。此方法避免遞迴堆疊溢出，適合處理極深的樹，但需完整遍歷所有節點（不像 BFS 可提前結束）。 - 時間複雜度：O(n)，空間複雜度：O(n)
延伸思考
- 若改為求最大深度（即到最遠葉節點的路徑長度），解法需要如何修改？單側子樹為 null 的情況處理方式是否相同？
- 為什麼 BFS 在求「最小深度」時比 DFS 更有效率？能否舉例說明 BFS 提前結束的場景？
- 若允許路徑不必從根節點出發，而是從任意節點出發到任意葉節點，最短路徑的計算方式應如何調整？