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
Tree Depth-first Search 链接: 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
更多讨论
https://discuss.leetcode.com/category/119/minimum-depth-of-binary-tree