Fun and tiny C++ iterative solution 4ms


  • 0
    C
    //For each node, bool indicates whether I am in one of two phases
    //1. bool == true phase:  I push (root, false), (right, true), (left, true) onto myStack
    //2. bool == false phase: I push my value on retval, and pop myself
    
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> retval;
            vector<pair<TreeNode*, bool> > myStack;       //to simulate recursion stack
            
            myStack.push_back(make_pair(root, true));
            while (!myStack.empty()) {
                auto inspect = myStack.back(); myStack.pop_back();
                TreeNode* me = inspect.first;
                if (me == NULL) continue;
                if (inspect.second == true) {
                    myStack.push_back(make_pair(me, false));
                    myStack.push_back(make_pair(me->right, true));
                    myStack.push_back(make_pair(me->left, true));
                } else {
                    retval.push_back(me->val);
                }
            }
            return retval;
        }
    };

Log in to reply
 

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