Problem 111 Minimum Depth of Binary Tree
该问题属于二叉树问题,简单来说就是找二叉树中左右子树最浅的层数,最初的思路就是以root为界分为左右,然后左右递归,每深入一层就将层数+1,最后选取左右子树中较浅的层数。
这其中需要注意几种情况:
- root为空
- root为叶子节点
- root的左子树或右子树为空
- root的左右子树均不为空
- 针对第一种情况自然是直接返回0
- 针对第二种情况就直接返回表示层数的i
- 针对第三种情况当左子树为空时就只能考虑右子树的深度,当右子树为空时就只能考虑左子树的深度,故此时应该返回max(左子树深度,右子树深度),否则肯定会出现返回不存在的左子树或右子树的情况
- 针对第四种情况就是完全二叉树,此时直接将层数+1并返回即可
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int i = 1;
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}else if(root.left==null&root.right==null){
return i;
}else if(root.left==null||root.right==null){
return Math.max(minDepth(root.left)+1,minDepth(root.right)+1);
}else{
return Math.min(minDepth(root.left)+1,minDepth(root.right)+1);
}
}
}