iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 20
1
Software Development

從LeetCode學演算法系列 第 20

[Day 20] 從LeetCode學演算法 - 0111. Minimum Depth of Binary Tree (Easy)

目標:
這題主要目的在於讓讀者更清楚樹的深度(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)


上一篇
[Day 19] 從LeetCode學演算法 - 0124. Binary Tree Maximum Path Sum (Hard)
下一篇
[Day 21] 從LeetCode學演算法 - 0110. Balanced Binary Tree (Easy)
系列文
從LeetCode學演算法30

1 則留言

0
hyj1116
iT邦新手 4 級 ‧ 2019-10-07 22:24:03

不是很明白這段:


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

為何不都使用min? /images/emoticon/emoticon13.gif

Desolve iT邦新手 5 級 ‧ 2019-10-07 23:33:32 檢舉

max那段是對應到java的這段:

if (l == 0 || r == 0) {
    return l + r + 1;
} 

所以其實也是在取有值的那條路(棄掉NIL那段)並加1,
因為當中比較小的會是0。

我要留言

立即登入留言