C 4ms dfs and bfs solutions


  • 0
    B

    Recursive DFS

    bool isSymmetricSubTrees(struct TreeNode* l, struct TreeNode* r)
    {
        if (!l && !r)
            return true;
        if (!l || !r)
            return false;
        if (l->val != r->val)
            return false;
        return (isSymmetricSubTrees(l->left, r->right) && isSymmetricSubTrees(l->right, r->left));
    }
    
    bool isSymmetric(struct TreeNode* root) 
    {
        if (!root)
            return true;
        return isSymmetricSubTrees(root->left, root->right);
    }
    

    BFS:

    bool isSymmetric(struct TreeNode* root) 
    {
        if (!root)
            return true;
            
        int size=2;
        struct TreeNode** curLine;
        
        curLine = malloc(size*sizeof(struct TreeNode));
        curLine[0] = root->left;
        curLine[1] = root->right;
        
        while(1)
        {
            int ix = 0;
            struct TreeNode** newLine = malloc(2*size*sizeof(struct TreeNode));
            
            for(int i=0;i<size;i+=2)
            {
                if (!curLine[i] && !curLine[i+1])
                    continue;
    
                if (!curLine[i] || !curLine[i+1])
                {
                    free(newLine);
                    free(curLine);
                    return false;
                }
                
                if (curLine[i]->val != curLine[i+1]->val)
                {
                    free(newLine);
                    free(curLine);
                    return false;
                }
                
                newLine[ix++] = curLine[i]->left;
                newLine[ix++] = curLine[i+1]->right;
                newLine[ix++] = curLine[i]->right;
                newLine[ix++] = curLine[i+1]->left;
            }
            
            if (!ix)
            {
                free(newLine);
                free(curLine);
                return true;
            }
            
            size = ix;
            free(curLine);
            curLine = newLine;
        }
    }
    

Log in to reply
 

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