EasyRating 1248

111. Minimum Depth of Binary Tree

treedepth-first-searchbreadth-first-searchbinary-tree

在 LeetCode 上作答 ↗

解題說明

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 提前結束的場景？
若允許路徑不必從根節點出發，而是從任意節點出發到任意葉節點，最短路徑的計算方式應如何調整？