0111. Minimum Depth of Binary Tree - chasel2361/leetcode GitHub Wiki

***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.

這個問題要求最小的深度，跟前面一題有點類似，但是由根出發所以狀況簡單一點。

解法可以從根出發，一直往深度較小的方向走到最後就可以知道答案，而問題就在於如何求出每個節點的最小深度。這裡可以使用遞迴法，不停地檢查每個節點的最小深度，如果左右子樹皆存在，就把左右子樹的節點丟進函示遞迴求出最小深度，取較少的那個值 + 1 (根也算深度)；如果左右子樹僅存其一，便求他的最小深度 + 1，如果遇到葉子 (左右子樹皆不存在) 就回傳 0 並停止遞迴。寫作程式碼大概會長這樣：

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

這樣寫的時間跟空間複雜度都是O(N)，在最糟的狀況下要遞迴 N 次才會得出結果

---

上面的寫法雖然是正確的，但上傳之後竟然只有比 7.49% 的案例快，那我只好研究一下其他人怎麼寫的，發現上面的寫法如果左右子樹僅有一者的話，還是會把兩邊都丟下去函式裡跑，只是不存在的那個會回傳0，這個部分就比較浪費效能跟空間，所以把判定寫得仔細一點，如果僅有其一，就只把另一邊丟進函式裡跑，速度就快了不少，贏了 88.26% 的案例欸，這就是所謂的牽一髮動全身ㄇ

(´⊙ω⊙`)

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