Recursive and non-recursive solutions in C, both accepted as best


  • 1
    struct TreeNode** fillNext( struct TreeNode** stack, int size , int* newSize)
    {
        struct TreeNode** t = ( struct TreeNode** )malloc(sizeof( struct TreeNode* )*2*size);
        int index = 0;
        for(int i = 0; i < size; i++)
        {
            if(stack[i])
            {
                t[index++] = stack[i]->left;
                t[index++] = stack[i]->right;
            }
        }
        *newSize = index;
        return t;
    }
    
    //AC - 4ms;
    bool isSymmetric( struct TreeNode * root )
    {
        if(!root || (!(root->left) && !(root->right))) return true;
        if(!root->left || !root->right) return false;
        int count = 1;
        struct TreeNode **lStack = ( struct TreeNode** )malloc(sizeof( struct TreeNode* ));
        lStack[0] = root->left;
        struct TreeNode **rStack = ( struct TreeNode** )malloc(sizeof( struct TreeNode* ));
        rStack[0] = root->right;
        while(count)
        {
            int lIndex = 0, rIndex = 0;
            for(int i = 0; i < count; i++)
            {
                if(!lStack[i] || !rStack[count-i-1])
                {
                    if(!lStack[i] && !rStack[count-i-1])
                        continue;
                    return false;
                }
                if(lStack[i]->val != rStack[count-i-1]->val)
                    return false;
            }
            int lCount=0, rCount=0;
            lStack = fillNext(lStack, count, &lCount);
            rStack = fillNext(rStack, count, &rCount);
            if(lCount != rCount) return false;
            count = lCount;
        }
        return true;
    }
    

    bool symmetric( struct TreeNode* left, struct TreeNode* right )
    {
        if(!left && !right) return true;
        else if(!left || !right) return false;
        if(left->val != right->val) return false;
        return symmetric(left->right, right->left) && symmetric(left->left, right->right);
    }
    //AC - 4ms;
    bool isSymmetric( struct TreeNode * root )
    {
        if(!root) return true;
        return symmetric(root->left, root->right);
    }

  • 0
    P

    I submit my code,and yours too;both 4ms..But there are some using 1ms just. I don't know how they can.


  • 0

    Sometimes, the time cost in the OJ is not quite stable. In most cases, as long as you have achieved the second best, yours then is already the best solution. Of course, at times you can still optimise your code in some aspects but readability and performance can not always be together hand in hand. It's then your own favour to choose between them.


  • 0
    B

    Non-recursive solution is definitely not optimal and it leaks memory.


  • 0

    @B1aze If you truly are afraid of that memory leaking issue, then you can just add free(stack) before fillNext return.


  • 0
    S
    This post is deleted!

  • 0

    @sleepzZ Why?


  • -1
    S
    This post is deleted!

  • 1

    @sleepzZ Huh? LHearen's original also won't run the second recursion in that case. Your version is exactly equivalent[*], it's just longer and worse code.

    [*] Except that yours is currently wrong, thanks to that extra semicolon.


  • 0
    S
    This post is deleted!

  • 0
    S

    sharing my recursive one

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if(!root)
                return true;
            return symmetric(root->left,root->right);
        }
    private:
        bool symmetric(TreeNode* left,TreeNode* right)
        {
            if(left==NULL || right==NULL)
                return left==right;
            if(left->val==right->val)
                return symmetric(left->left,right->right) && symmetric(left->right,right->left);
            return false;
        }
    };

Log in to reply
 

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