Help about "Minimum Depth of Binary Tree" problem solution


  • 1
    J

    I used recursive method to compute each node's depth. Here is my code:

    public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        int i = getMinDepth(root.left);
        int j = getMinDepth(root.right);
        if(i == 0 || j == 0)
            return 1+i+j;
        return Math.min(i,j) + 1;
    }
    
    private int getMinDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.min(getMinDepth(root.left), getMinDepth(root.right)) + 1;
    }
    

    }

    this code can not pass the input {1,2,3,4,#,#,5}. Expected is 3, but my output is 2.

    And also I can not know the input {1,2,3,4,#,#,5} is inorder Traversal or postorder or preorder.


  • 6
    M

    {1,2,3,4,#,#,5} is a modified level-order traversal. It is defined in http://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/, as well as in a few other places, but is basically a level-order traversal where #means the line of descent ends, so no more entries come from it.

    This tree looks like this:

        1
      2   3
    4       5
    

    Your algorithm currently finds the minimum depth of a null, not the minimum leaf. You account for the possibility of a null in minDepth(), but not in getMinDepth(), so it advances to 2-3 layer and the switches to getMinDepth, returning 1 for the depth of 2-3.

       minDepth(1)
          ->getMinDepth(2)
               ->getMinDepth(4)
                   ->1
               ->getMinDepth(null)
                   ->0
               return min(0,1)+1 = 1
         return min...+1 = 2
    

    In order to fix this, change this:

    int i = getMinDepth(root.left);
    int j = getMinDepth(root.right);
    

    To this:

    int i = minDepth(root.left);
    int j = minDepth(root.right);
    

    You can get rid of getMinDepth().


  • 0
    J

    Thank you for the explanation. Help me a lot :)


Log in to reply
 

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