Minimum Depth of Binary Tree leetcode java-蒲公英云

Minimum Depth of Binary Tree leetcode java

题目：

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.

题解：

递归解法急速判断左右两边子树哪个depth最小，要注意如果有个节点只有一边孩子时，不能返回0，要返回另外一半边的depth。

递归解法：

1 public int minDepth(TreeNode root) {
2 if(root == null)
3 return 0;
4 int minleft = minDepth(root.left);
5 int minright = minDepth(root.right);
6 if(minleft==0 || minright==0)
7 return minleft>=minright?minleft+1:minright+1;
8 return Math.min(minleft,minright)+1;
9 }

非递归解法：

1 public int minDepth(TreeNode root) {
2 if(root == null)
3 return 0;
4
5 int depth = 1;//The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
6 LinkedList queue = new LinkedList();
7 queue.add(root);
8 int curnum = 1;
9 int nextnum = 0;
10 while(!queue.isEmpty()){
11 TreeNode cur = queue.poll();
12 curnum—;
13
14 if(cur.left == null && cur.right == null)
15 return depth;
16
17 if(cur.left != null){
18 queue.add(cur.left);
19 nextnum++;
20 }
21
22 if(cur.right != null){
23 queue.add(cur.right);
24 nextnum++;
25 }
26
27 if(curnum == 0){
28 curnum = nextnum;
29 nextnum = 0;
30 depth++;
31 }
32 }
33 return depth;
34 }