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 }