目標：
這題主要目的在於讓讀者更清楚樹的深度(depth)的觀念。

原題：

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],
    3
   / \
  9  20
    /  \
   15   7
return its minimum depth = 2.

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

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

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

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:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int l = minDepth(root.left);
        int r = minDepth(root.right);
        if (l == 0 || r == 0) {
            return l + r + 1;
        } else {
            return Math.min(l, r) + 1;
        }
    }
}

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

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left or not root.right:
            return max(self.minDepth(root.left), self.minDepth(root.right)) + 1
        else:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(由於必須遍歷所有節點，時間複雜度為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學演算法，我們下次見囉，掰~

下篇預告：
0110. Balanced Binary Tree (Easy)