wayetan
12/30/2013 - 11:28 AM

## Minimum Depth of Binary Tree

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
*/

public class Solution{
public int minDepth(TreeNode root) {
return _minDepth(root, 1);
}
public int _minDepth(TreeNode root, int depth){
if(root == null)
return depth - 1;
int d_left = _minDepth(root.left, depth + 1);
int d_right = _minDepth(root.right, depth + 1);
if(d_left == depth)
return d_right;
if(d_right == depth)
return d_left;
return d_left < d_right ? d_left : d_right;
}
}``````
``````/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
q.offer(root);
q.offer(null);
int count = 1;
while(!q.isEmpty()){
TreeNode curr = q.poll();
if(curr != null){
if(curr.left == null && curr.right == null){
return count;
}
if(curr.left != null){
q.offer(curr.left);
}
if(curr.right != null){
q.offer(curr.right);
}
}else{
if(!q.isEmpty()){
count++;
q.offer(null);
}
}
}
return count;
}
}``````