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.
本题有两种解法。
第一种解法：对二叉树进行BFS，由于是按层遍历的，因此如果在某一层发现了一个叶子节点，那么就找到了最小深度，此时返回当前深度即可。实现代码如下：
1 public class Solution {
2 public int minDepth(TreeNode root) {
3 if (root == null) return 0;
4 int depth = 1;
5 int currentLevel = 1;
6 int nextLevel = 0;
7 Queue<TreeNode> queue = new LinkedList<TreeNode>();
8 queue.add(root);
9 while (!queue.isEmpty()) {
10 TreeNode node = queue.remove();
11 currentLevel--;
12 if (node.left == null && node.right == null) {
13 return depth;
14 }
15 if (node.left != null) {
16 queue.add(node.left);
17 nextLevel++;
18 }
19 if (node.right != null) {
20 queue.add(node.right);
21 nextLevel++;
22 }
23 if (currentLevel == 0) {
24 if (nextLevel != 0) {
25 depth++;
26 }
27 currentLevel = nextLevel;
28 nextLevel = 0;
29 }
30 }
31 return depth;
32 }
33 }
第二种解法：采用递归的思想，分别求左右子树的最小深度，比较之后返回较小值。实现如下：
1 public class MinimumDepthofBinaryTree {
2 public int minDepth(TreeNode root) {
3 if (root == null)
4 return 0;
5 if (root.left == null && root.right == null)
6 return 1;
7 else {
8 int leftDepth = root.left != null ? minDepth(root.left)
9 : Integer.MAX_VALUE;
10 int rightDepth = root.right != null ? minDepth(root.right)
11 : Integer.MAX_VALUE;
12 return Math.min(leftDepth, rightDepth) + 1;
13 }
14 }
15 }