Description
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Example
Given a binary tree as follow:
1
/ \
2 3
/ \
4 5
The minimum depth is 2.
题意：求二叉树的最小深度。至于这个最小深度该怎么理解呢？接触的比较多的是最大深度，即根结点到离它最远的叶子结点的距离（包括首尾），这里的距离当然是指结点的个数。显然，最小深度就是根结点到离它最近的结点之间距离。虽然知道是这个意思，在一开始的理解上还有点偏差。例如，我想如果根结点只有右子树，那么这个最小深度怎么算，是不是就是1了，因为左子树为空嘛。后来仔细想想，其实不然，左子树为空的话，如果右子树不为空，说明根结点（其他结点亦然）不是叶子点，还得继续求右子树的深度（对应于代码的第26和29行），直到遇到叶子结点。代码如下：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/**
* @param root: The root of binary tree
* @return: An integer
*/
public int minDepth(TreeNode root) {
// write your code here
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
if(root.left==null){
return minDepth(root.right)+1;
}
if(root.right==null){
return minDepth(root.left)+1;
}
return Math.min(minDepth(root.left),minDepth(root.right))+1;
}
}