Can my solution be optimized further??


  • 1
    A

    Even though it is a 0ms solution i think it can be optimized further because it traverse each element twice and requires extra space (by including int for each node).

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<pair<TreeNode*,int> > q;
        while(1)
        {
            while(root!=NULL)
            {
                q.push(make_pair(root,0));
                root=root->left;
            }
            if(q.empty()==true)              
            {
                break;
            }
            pair<TreeNode*,int> p=q.top();
            if(p.second==0)            //1st time access
            {
                q.top().second=1;
                root=p.first->right;
            }
            else                             //2nd time access add it to solution
            {
                q.pop();
                v.push_back(p.first->val);
            }
        }
        return v;
    }
    

    PS:Thanks in advance.


Log in to reply
 

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