Concise Java Recursive Solution


  • 0
    M
    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 + Math.min(minDepth(root.left), minDepth(root.right));
    	}

  • 0
    K

    It's indeed very clean and concise :)

    The problem is You are traversing using DFS instead of BFS,
    meaning You can end up traversing whole branch with 1 billion of nodes even if there is a single node in the second branch.


  • 0
    M

    You are definitely right. Actually this solution is not very efficient. A field carrying current min can be used to terminated search. Or use an iterative BFS solution can work without setting a field.


  • 0
    S
     if (root.left == null && root.right == null)
            return 1;
    

    This line is not required.


  • 0
    M

    Great observation~~ Thank you very much~~It's not needed. However, I was trying to avoid unnecessary function calls on null node, sometimes it saves a lot of time because the number of nodes at the bottom level of tree are about half of number of all nodes of tree. Save these function calls on null node sometimes saves a lot of time.


Log in to reply
 

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