My solution used level-order traversal


  • 42
    T

    level-order traversal and record current level depth, when meet a node which both child is null then return, no need to go farther

    public class Solution {
    public int minDepth(TreeNode root) {
    	if (root == null)
    		return 0;
    	int depth = 1;
    	Queue<TreeNode> queue = new LinkedList<TreeNode>();
    	TreeNode temp,magic = new TreeNode(0);
    	queue.add(root);
    	queue.add(magic);
    	while(!queue.isEmpty()){
    		temp = queue.poll();
    		if(temp.equals(magic)){
    		    if(!queue.isEmpty()){
    		        depth++;
    			    queue.add(magic);
    		    }
    		    continue;
    		}
    		if(temp.left == null && temp.right == null)
    			return depth;
    		if(temp.left != null)
    			queue.add(temp.left);
    		if(temp.right != null)
    			queue.add(temp.right);
    	}
    	return depth;
    }
    }
    

    Any better solution?


  • -3
    Y

    Don't forget deleted those memories.


  • 4
    A

    I using recursion for solve this problem:

     int minDepth(TreeNode *root) {
        if (NULL == root) return 0;
        if (NULL == root->left && NULL == root->right) {
            return 1;
        }
        
        int minDepthTree = INT_MAX;
        if (NULL != root->left) {
            minDepthTree = min(minDepthTree, minDepth(root->left) + 1);
        }
        if (NULL != root->right) {
            minDepthTree = min(minDepthTree, minDepth(root->right) + 1);
        }
        
        return minDepthTree;
    }

  • 3
    E

    I think your solution is better than other recursive solutions using DFS-like method. There's no need to traverse all the nodes to get the min depth of a tree using BFS-like method.


  • 9
    Y

    I used two queues to avoid the confusing magic element.

    public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        //is an empty tree
        if(root.left == null && root.right == null)
            return 1;
            
        Queue<TreeNode> nQ = new LinkedList<TreeNode>();
        Queue<Integer> dQ = new LinkedList<Integer>();
        
        nQ.offer(root);
        dQ.offer(1);
        
        while(!nQ.isEmpty()){
            TreeNode curNode = nQ.poll();
            int curDepth = dQ.poll();
            
            if(curNode.left == null && curNode.right == null)
                return curDepth;
            if(curNode.left != null){
                nQ.offer(curNode.left);
                dQ.offer(curDepth+1);
            }
            if(curNode.right != null){
                nQ.offer(curNode.right);
                dQ.offer(curDepth+1);
            }
        }
        
        return -1;
    }}
    

  • 9
    M

    my solution using recursion in JAVA:

     public int minDepth(TreeNode root) {
       if(root == null)
    		return 0;
    		int left=minDepth(root.left);
    		int right=minDepth(root.right);
    		if(left==0)
    			return right+1;
    		if(right==0)
    			return left+1;
    	return left<right ? left+1:right+1;
    }

  • 0
    Y
    class Solution {
    public:
        int minDepth(TreeNode *root) {
           if (root == NULL) return 0;
           /*
           if (root->left == NULL && root->right == NULL) return 1;
           if (root->left == NULL) return 1+minDepth(root->right);
           if (root->right == NULL) return 1+minDepth(root->left);
           return 1 + min(minDepth(root->left), minDepth(root->right));
           */
           queue<TreeNode *> q;
           q.push(root);
           int cur = 1;
           int nxt = 0;
           int height = 1;
           while (!q.empty()) {
               TreeNode *top = q.front();
               q.pop();
               --cur;
               if (top->left == NULL && top->right == NULL) return height;
               if (top->left != NULL) { q.push(top->left); ++nxt; }
               if (top->right != NULL) { q.push(top->right); ++nxt; }
               if (cur == 0) {
                   cur = nxt;
                   nxt = 0;
                   ++height;
               }
               
           }
        }
    };

  • 1
    V

    This version of solution in Java includes two queues which are implemented as linked lists, for better readability. Time complexity is O(n) and Space Complexity is O(n)

    public class Solution {
        public int minDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
     
            LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
            LinkedList<Integer> counts = new LinkedList<Integer>();
     
            nodes.add(root);
            counts.add(1);
     
            while(!nodes.isEmpty()){
                TreeNode curr = nodes.remove();
                int count = counts.remove();
     
                if(curr.left != null){
                    nodes.add(curr.left);
                    counts.add(count+1);
                }
     
                if(curr.right != null){
                    nodes.add(curr.right);
                    counts.add(count+1);
                }
     
                if(curr.left == null && curr.right == null){
                    return count;
                }
            }
     
            return 0;
        }
    }

  • 43
    5

    My Java code with a BFS method. Besides the queue, only two variables are used.

        public int minDepth(TreeNode root) {
        if(root==null) return 0;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        TreeNode endOfLevel = root;
        int depth = 1;
        
        while( !queue.isEmpty() ) {
            TreeNode node = queue.remove();
            if(node.left==null && node.right==null) return depth;
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null)  queue.add(node.right);
            if(node == endOfLevel) {
                endOfLevel = node.right==null ? node.left : node.right;
                depth++;
            }
        }
        
        return depth;
    }

  • 0
    T

    how to understand return left<right ? left+1:right+1; why we need to add 1 for left or right min path?


  • 0
    M

    because it indicates there is another level underneath current node, and the add 1 is to take the next level into account.


  • 52
    J

    probably a easier level order using the size of queue to determine the depth

    public int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int depth = 1;
        while (!queue.isEmpty()){
            int size = queue.size(); // determine the loop size
            for (int i = 0; i< size; i++){
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null){
                    return depth;
                }
                if (node.left!=null){
                    queue.add(node.left);
                }
                if (node.right!=null){
                    queue.add(node.right);
                }
            }
            depth ++;
        }
        return depth;
    }

  • 0
    X
    public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        
        int minDepth = 0;
        TreeNode t = root;
        Queue<TreeNodeLevel> queue = new LinkedList<TreeNodeLevel>();
        TreeNodeLevel rootLevel = new TreeNodeLevel(root,1);
        queue.offer(rootLevel);
        while(queue.size() > 0)
        {
            TreeNodeLevel r = queue.poll();
            
            if(r.node.left == null&&r.node.right == null)
                return r.level;
            else
            {
                if(r.node.left != null)
                {
                    TreeNodeLevel rl = new TreeNodeLevel(r.node.left,r.level + 1);
                    queue.offer(rl);
                }
                if(r.node.right != null)
                {
                    TreeNodeLevel rr = new TreeNodeLevel(r.node.right,r.level + 1);
                    queue.offer(rr);
                }
            }
        }
        return Integer.MAX_VALUE;
    }
    class TreeNodeLevel
    {
        TreeNode node;
        int level;
        public TreeNodeLevel(TreeNode node,int level)
        {
            this.node = node;
            this.level = level;
        }
    }
    

    }


  • 1
    B

    A Python Code

    class Solution:
    # @param root, a tree node
    # @return an integer
    # Use BFS so that no need for recursion and faster trimming. 
    def minDepth(self, root):
        if root==None:
            return 0
        
        stack=[(root,1)]
        while len(stack)!=0:
            node=stack.pop(0)
            if node[0]==None:
                continue
            if node[0].left==None and node[0].right==None:
                return node[1]
            else:
                stack.append((node[0].left,node[1]+1))
                stack.append((node[0].right,node[1]+1))
            
            
        return 0
    

  • 0
    J

    My java solution without recursion:

    public class Solution {
            public int minDepth(TreeNode root) {
                
                if (root == null) {
                    return 0;
                }
                Queue<TreeNode> queue = new LinkedList<TreeNode>();
                TreeNode node = root;
                
                int cur = 0;
                int order = 1;
                int next = 0;
                int level = 1;
                
                queue.offer(node);
                
                while (!queue.isEmpty()) {
                    node = queue.poll();
                    cur++;
                    
                    if (node.left == null && node.right == null) {
                        return level;
                    }
                    
                    if (node.left != null) {
                        next++;
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        next++;
                        queue.offer(node.right);
                    }
                    if (cur == order) {
                        level++;
                        order = next;
                        next = 0;
                        cur = 0;
                    }
                }
                return level;
            }

  • 1
    D

    if you solution is not BFS for this problem, then yours is not an ideal solution. BFS reaches the minimal depth leaf node before DFS.


  • 0
    A

    Is the time complexity of this just O(n) ? Or is that just in worst case


  • 0
    X

    nice iterative solution using queue!


  • 0
    W
    This post is deleted!

  • 0
    R

    class Solution {
    public:
    int minDepth(TreeNode* root) {
    if(root == NULL) return 0;
    queue<TreeNode*> Queue;
    int len= 1;
    Queue.push(root);
    while(!Queue.empty())
    {
    int size= Queue.size();
    for(int i = 0;i<=size-1;i++)
    {
    TreeNode* p = Queue.front();
    Queue.pop();
    if(p->left != NULL)
    {

                    Queue.push(p->left);
                }
                
                if(p->right != NULL) 
                {
                    
                    Queue.push(p->right);
                }
                
                if(p->left ==NULL  && p->right == NULL)
                {
                    return len;
                }
            }
            if(!Queue.empty())
            {
                len++;
            }
        }
        return len;
    }

Log in to reply
 

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