Three ways to solve this problem. Tell me if you have other solutions.


  • 1

    1 Iterative:

    Use a stack to save all nodes from root to leave.
    First go along the left path and then go back and go along the right path.
    Keep track of last node popping out of stack to prevent infinite loop.

        public int minDepth(TreeNode root) {
            if(root==null)
                return 0;
                
            int min = Integer.MAX_VALUE;
            TreeNode cur=root;
            TreeNode pre=null;
            int depth=0;
            Stack<TreeNode> s = new Stack<>();
            while(!s.isEmpty() || cur!=null){
                while(cur!=null){
                    s.push(cur);
                    cur=cur.left;
                    depth+=1;
                }
                cur = s.peek();
                if(cur.left==null && cur.right==null)
                    min = Math.min(min, depth);
                if(cur.right!=null && cur.right!=pre){
                    cur=cur.right;
                }else{
                    pre = s.pop();
                    depth-=1;
                    cur=null;
                }
            }
            return min;
        }
    

    2 Recursive:

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

    3 DFS: Use a global int min to keep track of minimum depth

        int min=Integer.MAX_VALUE;
        public int minDepth(TreeNode root) {
            dfs(root,0);
            return min==Integer.MAX_VALUE?0:min;
        }
        
        public void dfs(TreeNode root, int depth){
            if(root==null) return;
            if(root.left==null && root.right==null)
                min = Math.min(min, depth+1);
            dfs(root.left, depth+1);
            dfs(root.right, depth+1);
        }

  • 0
    G

    vely vely goooooooooood!
    clear mind


  • 0

    Glad to help.


  • 0
    G

    the Iterative way to solve this problem is a classic dfs solution in Iterative way. why do people prefer to simulate the dfs process in binary-tree tranverse,other than implenment the Iterative way like dfs in graph, more generic way.the code will be much more clear to understand.can u tell me y?


Log in to reply
 

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