My Accepted code with C (Postorder traversal iteratively with ugly realloc)


  • 0
    O

    Unfriendly realloc is used, prealloc may be a improvement solution?

    int* postorderTraversal(struct TreeNode* root, int* returnSize) {
        if(root == NULL || returnSize == NULL)
            return NULL;
        
        struct TreeNode **stack = (struct TreeNode **)malloc(sizeof(struct TreeNode *));
        int *mark_stack = (int*)malloc(sizeof(int));
        struct TreeNode *top = NULL;
        struct TreeNode *entry = root;
        int height = 0;
        int *returnarray = (int *)malloc(sizeof(int));
        
        *returnSize = 0;
        
        while(height > 0 || entry)
        {
            if(entry)
            {
                stack = (struct TreeNode **)realloc(stack, sizeof(struct TreeNode *) * (height + 1));
                mark_stack = (int)realloc(mark_stack, sizeof(int) * (height + 1));
                mark_stack[height] = 0;
                stack[height++] = entry;
                printf("in height:%d\n", height);
                entry = entry->left;
            }
            else
            {
                top = stack[--height];
                if(top->right && mark_stack[height] == 0)
                {
                    mark_stack[height] = 1;
                    stack[height++] = top;
                    entry = top->right;
                }
                else
                {
                    returnarray = (int *)realloc(returnarray, sizeof(int) * (*returnSize + 1));
                    returnarray[*returnSize] = top->val;
                    *returnSize += 1;
                }
            }
        }
        
        if(stack)
            free(stack);
        
        return returnarray;
    }
    

Log in to reply
 

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