题目：
111. Minimum Depth of Binary Tree(easy)
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.
Note: A leaf is a node with no children.
Example:1
2
3
4
5
6
7
8Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
题目大意：
找出二叉树中从根到叶中最短的路径。
解题思路：
递归求得当前结点的两个子树的长度，取得最小的数值加1，要注意的是单独处理一些特殊情况，增强程序健壮性。
后来在labuladong大佬讲解BFS框架中，获知了用BFS的方法求二叉树的最小深度的代码框架，更觉得其实这个思路才是最容易想到和最直观理解的。代码也是理解BFS最典型的框架代码。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37递归(DFS)
Java:
public int minDepth(TreeNode root){
if(root == null) return 0;
if(root.left == null && root.right == null) return 1;
int left = minDepth(root.left);
int right = minDepth(root.right);
if(left == 0 || right == 0) return left + right + 1;
/* 这条是为了过 [1,2]这种只有单子树的例子，即根1只有2一个子结点且为叶子结点,所以就是子树的长度加1 */
return Math.min(left,right) + 1;
/*取其中高度较小的分支为向下递归的方向，加上当前结点的高度1
*/
}
BFS:
public int minDepth(TreeNode root){
if(root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 1;
while(!q.isEmpty()){
int sz = q.size();
for(int i = 0; i < sz; i++){
TreeNode cur = q.poll();
if(cur.left == null && cur.right == null)
return depth;
if(cur.left != null)
q.offer(cur.left);
if(cur.right != null)
q.offer(cur.right);
}
depth ++;
}
return depth;
}
