1、前言
题目描述2、思路
此题比较简单,我们要学会用 DFS 跟 BFS 两种思路去解决,学会使用这两种思路很重要,因为有些题目 DFS 可以解决,但是有些只能是 BFS。
3、代码
BFS 思路:
/**
* 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 depth = 1;
List<TreeNode> queue = new ArrayList<>();
queue.add(root);
while(queue.size() > 0){
int size = queue.size();
// 这种写法就是将每层分的很清楚
for(int i = 0; i < size; i++){
TreeNode cur = queue.remove(0);
if(cur.left == null && cur.right == null){
return depth;
}
if(cur.left != null){
queue.add(cur.left);
}
if(cur.right != null){
queue.add(cur.right);
}
}
depth++;
}
return depth;
}
}
DFS 思路:
/**
* 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 left = minDepth(root.left);
int right = minDepth(root.right);
// 如果 root 的左右子树都为空,则 left、right = 0;如果任意一个为空,则 left、right 其中一个为0;
// 如果两个都不为空,那么选择其中最小的一个。
return root.left == null || root.right == null ?
left + right + 1 : Math.min(left, right) + 1;
}
}
网友评论