给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2.
看到这么简单的题，一顿操作，立马就写出了如下代码：
1
2
3
4
5
6
7
8
| class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
|
调试发现 [2,9]这个用例不对，我们得到的结果为 1，实际结果为 2。原因在于我们统计了空结点到根节点的深度。
对于每个结点，当只有一个子树时，直接返回子树的最小深度加一；当有两颗子树时，返回左右子树之中的最小深度加一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
if(root.left == null && root.right != null){
return minDepth(root.right) + 1;
}else if(root.right == null && root.left != null){
return minDepth(root.left) + 1;
}else{
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
}
|
时间复杂度O(n)，空间复杂度O(h)，h 为树的高度，当二叉树退化为链表时，空间复杂度O(n)。