Why [2,1]'s min depth is 2? I thought it should be 1.


  • 0
    B

    All other solutions that I saw are hardcoded to return 2 instead of 1 just on cases like [2,1] or [2,null,1]. Why my code is wrong?

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if(root == NULL)
                return 0;
            
            if(root->left == NULL || root->right == NULL)
                return 1;
    
            return min( 1 + minDepth(root->left), 1 + minDepth(root->right) );
        }
    };

  • 2
    A

    On case [2,1], root node of the tree doesn't have a leaf on its right sub tree. The nearest leaf node locates on its left sub tree, so the minimum should be 2.

    root->left == NULL || root->right == NULL
    

    It doesn't mean node root is a leaf node. The function should not return here. Only when node != NULL && its brother == NULL, the node is a leaf node.

    Here is my solution, similar to yours.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            return minDepth(root, false);
        }
    private:
        static int minDepth(TreeNode* root, bool hasbrother)
        {
            if(root==NULL) return hasbrother ? INT_MAX : 0;
            
            return 1+min(minDepth(root->left, root->right != NULL),
            minDepth(root->right, root->left != NULL));
        }
    };
    

    I wish you understand what I am talking about... My English is poor.
    Good Luck!


  • 0
    B

    Dear Angus4506, thank you


Log in to reply
 

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