来自Leetcode第111题二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2.
翻车现场
最开始以为是和最大深度那题差不多的，结果忽略了一种情况，即[1,2]这种根结点只有一个叶子结点的情况，这时最小深度应该是2，因为按题目定义根结点不能作为自己的叶结点，以下是初始代码
1
2
3
4
5
6
7
8
9
| public int minDepth(TreeNode root) {
if(root == null)
return 0;
else {
int left_height = minDepth(root.left);
int right_height = minDepth(root.right);
return Math.min(left_height,right_height) + 1;
}
}
|
递归
根据上面的分析，知道要在递归里做判断，判断是否是叶子结点,然后再进行递归
1
2
3
4
5
6
7
8
9
10
11
12
| public int minDepth(TreeNode root) {
if(root == null)
return 0;
else if(root.left == null && root.right == null)
return 1;
int minDepth = Integer.MAX_VALUE;
if(root.left != null)
minDepth = Math.min(minDepth,minDepth(root.left));
if(root.right != null)
minDepth = Math.min(minDepth,minDepth(root.right));
return minDepth + 1;
}
|
BFS迭代
利用一个队列进行层次遍历，用一个 level 变量保存当前的深度,只要在 for 循环中判断当前是不是叶子节点，如果是的话，返回当前的 level 就可以了。此外要把level初始化改为1，因为如果只有一个根节点，它就是叶子节点，而在代码中，level 是在 for循环以后才++的，如果被提前结束的话，此时应该返回1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public int minDepth(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> ans = new LinkedList<List<Integer>>();
if(root == null)
return 0;
queue.offer(root);
int level = 1;
while (!queue.isEmpty()){
int levelNum = queue.size();
for(int i = 0 ; i < levelNum ; i++){
TreeNode tmp = queue.poll();
if(tmp != null) {
if (tmp.left == null && tmp.right == null)
return level;
if (tmp.left != null)
queue.offer(tmp.left);
if(tmp.right != null)
queue.offer(tmp.right);
}
}
level ++;
}
return level;
}
|