DAY 20
1
Software Development

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

(節點是指它底下沒有其他小孩了)

(因為從根走到根的左/右節點要計算到)

``````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))

「可以用迭代解嗎？」

0110. Balanced Binary Tree (Easy)

### 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
``````

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

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

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