從LeetCode學演算法

0111. Minimum Depth of Binary Tree (Easy)

Question

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its minimum depth = 2.

分析/解題

題目給定一個二元樹，要求找到最小的深度，也就是從根節點到最近的葉節點的路徑長。(葉節點是指它底下沒有其他小孩 了)
上一題我們講解了一題Hard的題目，讓我們稍微喘口氣，
來看個這個比較基本的題目吧！

這題概念並不複雜，只要稍微弄明白要被遞迴的主體即可。
對一個節點來說，我們已經知道所謂的深度就是從根走到這個節點的長度 。
既然我們要求最小的路徑長度，可以選擇的方式就是分別看兩邊有多深，
最後選擇較小的那邊 ，加上1即可。(因為從根走到根的左/右節點要計算到)
那麼，左右各自有多深同樣也要取最小的路徑，
故一樣使用相同的方法再往下遞迴。

依此嘗試寫成遞迴的虛擬碼：

1
2
3
4
5
6
7
8
9
minDepth(root) {
  if root == NIL return 0
  l = minDepth(root.left)
  r = minDepth(root.right)
  if l == 0 or r == 0
    return l + r + 1     // 等同於取非NIL那條的路徑或取1(當左右都是NIL)
  else
    return min(l, r) + 1 // 左右都有時取較小的路徑
}

再化成程式碼如下：

Java

Python的部分使用判斷是否是None來處理，
本質上是一樣的，讀者可依個人喜好來選用寫法。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(由於必須遍歷所有節點，時間複雜度為O(N)，空間複雜度則依照stack深度而定，最糟的狀況也是O(N)，最好的狀況則是O(logN))

「可以用迭代解嗎？」
可以，但比較難想，有興趣的讀者可以嘗試使用我們還沒有仔細講過的level-order traversal 來解此題，大致的思路是使用Queue來保存相同深度的所有節點 ，並且用另一個Queue和level進行記錄，一旦在某次出現了node.left和node.right均為NIL 的狀況，代表在這層就遇到葉子，那麼就可以回傳level即為解答 。
這麼做的時間複雜度和空間複雜度均和最小深度 有關，若最小深度為D，
時間空間複雜度均為O(2^D)，雖然看起來比較可怕，
但其實最糟的狀況是這棵二元樹是平衡的，這時2^D-1 = N；
而其他狀況下複雜度肯定小於O(N)。

從LeetCode學演算法，我們下次見囉，掰~