Java Solution, recursive & Iteration(BFS)


  • 5
    1. recursive , need to rule out the null child.

       public int minDepth(TreeNode root) {
       if(root==null)
           return 0;
       int depth=0;
       if(root.left!=null&&root.right!=null){
           int lh=minDepth(root.left);
           int rh=minDepth(root.right);
           depth=Math.min(lh,rh);
       }
       else if(root.left!=null){
           depth=minDepth(root.left);
       }
       else if(root.right!=null){
           depth=minDepth(root.right);
       }
       
       return depth+1;
      

      }

    2. Iteration(BFS), no need to access all the tree nodes.

       public int minDepth(TreeNode root) {
       int depth=0;
       if(root==null)
           return depth;
       Queue<TreeNode> q=new LinkedList<TreeNode>();
       q.offer(root);
       while(q.peek()!=null){
           depth++;
           int size=q.size();
           for(int i=0;i<size;i++){
                TreeNode node=q.poll();
                if(node.left==null&&node.right==null)  
                   return depth;
                if(node.left!=null)
                   q.offer(node.left);
                if(node.right!=null)
                   q.offer(node.right);
           }
          
       }
       return 0;
      

      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.