3 java solutions include recursive,BFS,DFS


  • 2
    Q

    recursive:

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

    BFS:

    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        int size,level=1;
        TreeNode tn;
        while(!queue.isEmpty()){
            size=queue.size();
            for(int i=0;i<size;i++){
                tn=queue.remove();
                if(tn.left==null&&tn.right==null){
                    return level;
                }else{
                    if(tn.left!=null) queue.add(tn.left);
                    if(tn.right!=null) queue.add(tn.right);
                }
            }
            level++;
        }
        return level;
    }
    

    DFS:

    public int minDepth(TreeNode root){
        if(root==null) return 0;
        Stack<TreeNode> stack=new Stack<TreeNode>();
        TreeNode tp,lastVisited=null,n;
        int min=Integer.MAX_VALUE;
        while(root!=null||!stack.isEmpty()){
            if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
                tp=stack.peek();
                if(tp.right!=null&&tp.right!=lastVisited){
                    root=tp.right;
                }else{
                    if(tp.left==null&&tp.right==null){
                        if(stack.size()<min) min=stack.size();
                    }
                    lastVisited=stack.pop();
                }
            }
        }
        return min;
    }

  • 0
    H

    Really nice and cool solution!!!


Log in to reply
 

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