A queue solution with best submission (4ms) and a recursive solution (8ms) with simplicity in C


  • 1
    //AC - 8ms;
    int minDepth( struct TreeNode* root )
    {
        if(!root) return 0;
        if(!root->left && !root->right) return 1;
        int lDepth=INT_MAX, rDepth=INT_MAX;
        if(root->left)
            lDepth = minDepth(root->left)+1;
        if(root->right)
            rDepth = minDepth(root->right)+1;
        return lDepth > rDepth? rDepth : lDepth;
    }
    
    //AC - 4ms;
    int minDepth( struct TreeNode* root )
    {
        if(!root) return 0;
        if(!root->left && !root->right) return 1;
        struct TreeNode** queue0 = ( struct TreeNode** )malloc(sizeof( struct TreeNode* ));
        struct TreeNode** queue1 = ( struct TreeNode** )malloc(sizeof( struct TreeNode* ));
        int size = 1;
        int level = 1;
        queue0[size-1] = root;
        while(size)
        {
            queue1 = ( struct TreeNode** )realloc(queue1, sizeof( struct TreeNode* )*2*size);
            int index = 0;
            for(int i = 0; i < size; i++)
            {
                if(!queue0[i]->left && !queue0[i]->right)
                    return level;
                if(queue0[i]->left)
                    queue1[index++] = queue0[i]->left;
                if(queue0[i]->right)
                    queue1[index++] = queue0[i]->right;
            } 
            level++;
            struct TreeNode** t = queue0;
            queue0 = queue1;
            queue1 = t;
            size = index;
        }
    }

Log in to reply
 

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