AUG^_^ My BFS(JAVA & Explaination), thought it will be faster than DFS, but it doesn't, you know why?


  • 2
    public int minDepth(TreeNode root) {
                    int res = 0 ;
    		if(root == null) return res;
    		LinkedList<TreeNode> queue = new LinkedList<>();//Always like linkedList
    		queue.offer(root);//offer the root
    		while(queue.size() > 0)//let do the level traverse
    		{
    			res++;// res add one when we are at a new level
    			int size = queue.size();//Remember the level size so you do not mess up
    			for(int i = 0 ; i < size ; i++)
    			{
    				TreeNode node = queue.poll();
    //If there is a node who do not have any child, then it is a leaf and we can stop here.
    				if(node.left == null&&node.right == null)
    					return res;
    //offer the child or children to the queue for the analysis of the next level
    				if(node.left != null)
    					queue.offer(node.left);
    				if(node.right != null)
    					queue.offer(node.right);
    			}
    		}
    		return res;
        }
    

    1 ms, not bad. If you like it, please thumb me up or leave you comments bellow to communicate.


  • 0

    Same solution but in Swift, 393 ms....


  • 0

    @zhugejunwei Wow, all right, don't know about that language. Is that a language offered by Apple? How good is that?


  • 0

    @Augustdoker I think it's pretty good. Many people said it's faster than java, but I didn't see that. :\


  • 2

    @zhugejunwei there are many extra considerations in the OJ for java, though it's slower but the major factors that contributes to that is removed. So here as you can see it's fast, even faster than C/C++.

    As for BFS and DFS, @Augustdoker using higher-level built-in class is always costing much more than you can imagine while a recursive DFS method here will be optimised by the underlying compiler.


  • 0

    @LHearen Thank you for your explanation.)


  • 0

    @LHearen Yeah, you are right, maintaining a linkedList may cost more than I think. And also,
    Level traverse does not traverse less nodes to find the answer in tons of cases. Thank you!


Log in to reply
 

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