I want to know my mistake


  • 0
    S

    here is my code:

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

  • 2
    P

    not every intermediate node has both left child and right child

    If it has no right child, for example, you shouldn't calculate midDepth(root.right) at all.

    public class Solution {
        public int minDepth(TreeNode root) {
        	int crtDepth = 0;
        	if (root != null) {
        		if (root.left == null) {
        			return 1 + minDepth(root.right);
        		}
        		else if (root.right == null) {
        			return 1 + minDepth(root.left);
        		}
        		int tmp1 = 1, tmp2 = 1;
        		tmp1 += minDepth(root.left);
        		tmp2 += minDepth(root.right);
        		crtDepth += tmp1 < tmp2 ? tmp1 : tmp2;
        	}
        	return crtDepth;
        }
    }

  • 0
    S

    the code : if (root != null)
    is for this question


  • 0
    P

    it didn't solve the question.
    Let me give you an example. Suppose an intermediate node has only left child but no right child. The minDepth of the left subtree is 7. Then you should return 8 for this node.

    However, since you call minDepth(root.right) as well and it will return 0 for sure because root.right == null, you will return 1, which is completely wrong.


  • 0
    S

    the var tmp1 and tmp2 init with 1 to express the current node not empty


  • 0
    S

    My english is poor, please forgive me


  • 0
    P

    Your basic logic is:

    1. If root is null, return 0

    2. If root is not null, return min(minDepth(root.left), minDepth(root.right)) + 1

    What I want to say is, the second point is wrong


  • 0
    S

    if left leaf node or right leaf node is empty, this code will return 0, but tmp1 and tmp2 always express this node is not empty


  • 0
    P

    see my edited post.

    You should handle the case when either left child is null or right child is null


  • 0
    S

    got it, thank you


  • 0
    S

    I have realized my mistake, in some cases I not find leaves, a node but find


Log in to reply
 

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