111. 二叉樹的最小深度
給定一個二叉樹，找出其最小深度。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例:
給定二叉樹 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
算法思路
這里先注意一下 1, 2 這個測試用例，寫在前面。
題目中的說明：葉子節(jié)點是指沒有子節(jié)點的節(jié)點，針對 1,2 這個測試案例，1 不是葉子節(jié)點，2 才是葉子節(jié)點。
解決這道題的關(guān)鍵是弄清楚遞歸終止條件：
- 葉子節(jié)點的定義是左孩子或者右孩子都為 null 時叫做葉子節(jié)點
- 當(dāng) root 節(jié)點左右孩子都為 null 時，返回 1
- 當(dāng) root 節(jié)點左右孩子有一個為空時，返回不為空的孩子節(jié)點的深度
- 當(dāng) root 節(jié)點左右孩子都不為空時， 返回左右孩子較小深度的節(jié)點值
方法1: DFS
class Solution {
// DFS 遞歸 + 分治 時間O(n) 空間O(n)
public int minDepth1(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right != null) {
return 1 + minDepth(root.right);
}
if (root.left != null && root.right == null) {
return 1+ minDepth(root.left);
}
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
方法2: BFS
class Solution {
// BFS 時間O(n) 空間O(n)
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
if (curr.left == null && curr.right == null) {
return level;
}
if (curr.left != null) queue.add(curr.left);
if (curr.right != null) queue.add(curr.right);
}
level++;
}
return -1;
}
}
以上謝謝大家，求贊求贊求贊！
