111. 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.

Solution:

It's similar to find the maximum depth.

1. Recursive solution

The difference between this problem and Maximum depth is that for Maximum, it will automatically/implicitly count the depth till the leaf, but for this problem we have to explicitly check if current node is leaf or not. If it is not leaf, we still need to go to the either left child or right child depends on the tree status.

 public int minDepth(TreeNode root) {  
     if(root==null) return 0;  
     if(root.left==null) return minDepth(root.right)+1;  
     if(root.right==null) return minDepth(root.left)+1;  
     return Math.min(minDepth(root.left),minDepth(root.right))+1;  
   }  

2. Iterative solution
Using the level order traversal. 
Just return the current level when the first leaf is processed. So we only need to check if current node is leaf, if yes, return the level. If no, continue as usual.

 public int minDepth(TreeNode root) {  
   if(root==null) return 0;   
   LinkedList<TreeNode> q=new LinkedList<TreeNode>();   
   q.offer(root);   
   int curL=0;   
   int lastL=1;   
   int lev=1;  
   while(!q.isEmpty()){   
    TreeNode cur=q.poll();   
    if(cur.left==null && cur.right==null) return lev;   
    lastL--;   
    if(cur.left!=null) {   
     q.offer(cur.left);   
     curL++;   
    }   
    if(cur.right!=null) {   
     q.offer(cur.right);   
     curL++;   
    }   
    if(lastL==0){   
     lev++;  
     lastL=curL;   
     curL=0;   
    }   
   }   
   return lev;     
   }