0ms iterative C solution, no reverse, self-implemented stack


  • 0
    C
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    typedef struct stack {
        void           *c;
        struct stack   *next;
    } Stack;
    
    void create(Stack **ptop)
    {
        *ptop = NULL;
    }
    
    void push(Stack **ptop, void *c)
    {
        Stack   *tmp;
    
        tmp = malloc(sizeof *tmp);
        tmp->c = c;
        tmp->next = *ptop;
    
        *ptop = tmp;
    }
    
    void pop(Stack **ptop, void **c)
    {
        Stack   *tmp;
    
        if (! *ptop) return;
    
        tmp = *ptop;
        if (c) *c = tmp->c;
        *ptop = (*ptop)->next;
        free(tmp);
    }
    
    void top(Stack **ptop, void **c)
    {
        *c = (*ptop)->c;
    }
    
    int empty(Stack **ptop)
    {
       return *ptop == NULL; 
    }
    
    void push_to_leftmost(Stack **s, struct TreeNode *root)
    {
        while (root) {
            push(s, root);
            root = root->left;
        }
    }
    
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    int* postorderTraversal(struct TreeNode* root, int* returnSize)
    {
        int             *arr;
        long            mark;
        Stack           *s;
        struct TreeNode *last;
        
        create(&s);
        arr = malloc(10000 * sizeof *arr);
        *returnSize = 0;
        last = NULL;
        
        push_to_leftmost(&s, root);
        while (!empty(&s)) {
            top(&s, &root);
    
            if (!root->right || last == root->right) {
                pop(&s, NULL);
                arr[(*returnSize)++] = root->val;
                last = root;
            } else {
                push_to_leftmost(&s, root->right);
            }
        }
        
        return arr;
    }
    

Log in to reply
 

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