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.
Note: A leaf is a node with no children.
Example:
Given binary tree
[3,9,20,null,null,15,7], 3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
https://leetcode.com/problems/minimum-depth-of-binary-tree/discuss/36045/My-4-Line-java-solution
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;
}
https://leetcode.com/problems/minimum-depth-of-binary-tree/discuss/36060/3-lines-in-Every-Language
public int minDepth(TreeNode root) {
if (root == null) return 0;
int L = minDepth(root.left), R = minDepth(root.right);
return 1 + (Math.min(L, R) > 0 ? Math.min(L, R) : Math.max(L, R));
}
public int minDepth(TreeNode root) {
if (root == null) return 0;
int L = minDepth(root.left), R = minDepth(root.right), m = Math.min(L, R);
return 1 + (m > 0 ? m : Math.max(L, R));
}
X. BFS
public int minDepth(TreeNode root) { if(root==null) return 0; ArrayList<TreeNode> last =new ArrayList<TreeNode>(); last.add(root); int count=1; while(!last.isEmpty()){ ArrayList<TreeNode> curr = new ArrayList<TreeNode>(); for(TreeNode n:last){ if(n.left==null && n.right==null) return count; if(n.left!=null) curr.add(n.left); if(n.right!=null) curr.add(n.right); } count++; last=curr; //new ArrayList<TreeNode>(curr); } return count; }http://codeganker.blogspot.com/2014/02/minimum-depth-of-binary-tree-leetcode.html
Maintain count of current level and next level, switch them after finish current level.
public int minDepth(TreeNode root) { if(root == null) return 0; LinkedListqueue = new LinkedList (); int curNum = 0; int lastNum = 1; int level = 1; queue.offer(root); while(!queue.isEmpty()) { TreeNode cur = queue.poll(); if(cur.left==null && cur.right==null) return level; lastNum--; if(cur.left!=null) { queue.offer(cur.left); curNum++; } if(cur.right!=null) { queue.offer(cur.right); curNum++; } if(lastNum==0) { lastNum = curNum; curNum = 0; level++; } } return 0; }
public int minDepth(TreeNode root) { if(root == null){ return 0; } LinkedList<TreeNode> nodes = new LinkedList<TreeNode>(); LinkedList<Integer> counts = new LinkedList<Integer>(); nodes.add(root); counts.add(1); while(!nodes.isEmpty()){ TreeNode curr = nodes.remove(); int count = counts.remove(); if(curr.left != null){ nodes.add(curr.left); counts.add(count+1); } if(curr.right != null){ nodes.add(curr.right); counts.add(count+1); } if(curr.left == null && curr.right == null){ return count; } } return 0; }
https://leetcode.com/discuss/6308/my-solution-used-level-order-traversal
Maintain endOfLevel tree node
public int minDepth(TreeNode root) { if(root==null) return 0; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); TreeNode endOfLevel = root; int depth = 1; while( !queue.isEmpty() ) { TreeNode node = queue.remove(); if(node.left==null && node.right==null) return depth; if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); if(node == endOfLevel) { endOfLevel = node.right==null ? node.left : node.right; depth++; } } return depth; }
While+for loop to loop all current layer nodes
public int minDepth(TreeNode root) { if (root == null){ return 0; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); int depth = 1; while (!queue.isEmpty()){ int size = queue.size(); // determine the loop size for (int i = 0; i< size; i++){ TreeNode node = queue.poll(); if (node.left == null && node.right == null){ return depth; } if (node.left!=null){ queue.add(node.left); } if (node.right!=null){ queue.add(node.right); } } depth ++; } return depth; }
Using magic node
public int minDepth(TreeNode root) { if (root == null) return 0; int depth = 1; Queue<TreeNode> queue = new LinkedList<TreeNode>(); TreeNode temp,magic = new TreeNode(0); queue.add(root); queue.add(magic); while(!queue.isEmpty()){ temp = queue.poll(); if(temp.equals(magic)){ if(!queue.isEmpty()){ depth++; queue.add(magic); } continue; } if(temp.left == null && temp.right == null) return depth; if(temp.left != null) queue.add(temp.left); if(temp.right != null) queue.add(temp.right); } return depth; }
http://yucoding.blogspot.com/2013/01/leetcode-question-55-minimum-depth-of.html
Store node and level in Queue.
int minDepth(TreeNode *root) { queue< pair<TreeNode*,int> > q; int i=0; if (!root){return 0;} q.push(make_pair(root,1)); while(!q.empty()){ pair<TreeNode*,int> cur = q.front(); q.pop(); if (!cur.first->left && !cur.first->right){ return cur.second; } if(cur.first->left){ q.push(make_pair(cur.first->left,cur.second+1)); } if(cur.first->right){ q.push(make_pair(cur.first->right,cur.second+1)); } } }http://www.jiuzhang.com/solutions/minimum-depth-of-binary-tree/
public int minDepth(TreeNode root) { if (root == null) { return 0; } return getMin(root); } public int getMin(TreeNode root){ if (root == null) { return Integer.MAX_VALUE; } if (root.left == null && root.right == null) { return 1; } return Math.min(getMin(root.left), getMin(root.right)) + 1; }https://discuss.leetcode.com/topic/8723/my-4-line-java-solution/
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;
}Time complexity of above solution is O(n) as it traverses the tree only once.
public int minDepth(TreeNode root) { if(root==null) return 0; if(root.left==null && root.right==null) return 1; if(root.left==null){ return 1+minDepth(root.right); }else if(root.right==null){ return 1+minDepth(root.left); }else return 1+Math.min(minDepth(root.left), minDepth(root.right)); }Related: Maximum Height (Depth) of a Binary Tree | LeetCode
Read full article from LeetCode – Minimum Depth of Binary Tree (Java)
