Very typical solution using one stack in C, accepted as best


  • 0
    #define LEN 1000
    int* postorderTraversal(struct TreeNode* root, int* returnSize)
    {
        *returnSize = 0;
        if(!root) return NULL;
        int* arr = (int*)malloc(sizeof(int)*LEN);
        struct TreeNode **stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*LEN);
        int top = -1;
        stack[++top] = root;
        struct TreeNode *pre = NULL;
        while(top > -1)
        {
            struct TreeNode *cur = stack[top];
            if(!pre || pre->left==cur || pre->right==cur)
            {
                if(cur->left) stack[++top] = cur->left;
                else if(cur->right) stack[++top] = cur->right;
                else arr[(*returnSize)++] = cur->val, top--;
            }
            else if(cur->left == pre)
            {
                if(cur->right) stack[++top] = cur->right;
                else arr[(*returnSize)++] = cur->val, top--;
            }
            else if(cur->right == pre)
                arr[(*returnSize)++] = cur->val, top--;
            pre = cur;
        }
        return arr;
    }

  • 0

    Corresponding C++ version

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) 
        {
            if(!root) return vector<int>();
            stack<TreeNode*> node_stack;
            vector<int> v;
            node_stack.push(root);
            TreeNode *pre = NULL, *cur = NULL;
            while(!node_stack.empty())
            {
                cur = node_stack.top();
                if(!pre || pre->left==cur || pre->right==cur)
                {
                    if(cur->left) node_stack.push(cur->left);
                    else if(cur->right) node_stack.push(cur->right);
                    else { v.push_back(cur->val); node_stack.pop(); }
                }
                else if(cur->left == pre)
                {
                    if(cur->right) node_stack.push(cur->right);
                    else { v.push_back(cur->val); node_stack.pop(); }
                }
                else if(cur->right == pre)
                {
                    v.push_back(cur->val);
                    node_stack.pop();
                }
                pre = cur;
            }
            return v;
        }
    };
    

Log in to reply
 

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