111. Minimum Depth of Binary Tree

题目：

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.

Hide Tags

链接： http://leetcode.com/problems/minimum-depth-of-binary-tree/

一刷，按层判断

 1 class Solution(object):
 2     def minDepth(self, root):
 3         if not root:
 4             return 0
 5         
 6         prev = [root]
 7         cur = []
 8         depth = 1
 9         while prev:
10             for elem in prev:
11                 if not elem.left and not elem.right:
12                     return depth
13                 if elem.left:
14                     cur.append(elem.left)
15                 if elem.right:
16                     cur.append(elem.right)
17             depth += 1
18             prev, cur = cur, []
19         return depth

2/17/2017, Java, performance不好

错误：判断时候要注意是否是叶节点，而不是一边是null，一边有子树

 1 public class Solution {
 2     public int minDepth(TreeNode root) {
 3         if (root == null) return 0;
 4         Queue<TreeNode> level = new LinkedList<>();
 5         TreeNode node = new TreeNode(-1);
 6         int size;
 7         int index = 0;
 8         
 9         level.add(root);
10         while(!level.isEmpty()) {
11             index++;
12             size = level.size();
13             for (int i = 0; i < size; i++) {
14                 node = level.poll();
15                 if (node.left == null && node.right == null) return index;
16                 if (node.left != null) level.add(node.left);
17                 if (node.right != null) level.add(node.right);
18             }
19         }
20         return index;
21     }
22 }

5/11/2017

算法班

注意：

1. Queue是接口，用LinkedList实现

2. Queue的方法是add/poll/remove等等

3. 判断LinkedList是否为空，isEmpty与stack.empty有不同

 1 public class Solution {
 2     public int minDepth(TreeNode root) {
 3         if (root == null) return 0;
 4         
 5         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 6         TreeNode node;
 7         queue.add(root);
 8         int index = 0;
 9         while (!queue.isEmpty()) {
10             index++;
11             int size = queue.size();
12             for (int i = 0; i < size; i++) {
13                 node = queue.poll();
14                 if (node.left == null && node.right == null) return index;
15                 if (node.left != null) {
16                     queue.add(node.left);
17                 }
18                 if (node.right != null) {
19                     queue.add(node.right);
20                 }
21             }
22         }
23         return index;
24     }
25 }

别人的做法

递归

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

https://discuss.leetcode.com/topic/8723/my-4-line-java-solution

https://discuss.leetcode.com/topic/16869/3-lines-in-every-language