clean C++ one-stack solution. no abuse on input, no record of previous values


  • 0

    Push the node under traversal as well as its right child into the stack at the same time so that we can tell if the node under traversal needs to be collected already.

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<pair<TreeNode*,TreeNode*>> v; //as a stack
            vector<int> ret;
            for(;root;root = root->left) v.push_back({root,root->right});
    #define ROOT first
    #define RIGHT second
            while(!v.empty()) {
                auto& p = v.back();
                if(p.RIGHT) {
                    root = p.RIGHT;
                    p.RIGHT = NULL; //when next time we meet, i will put you into the vector
                    for(;root;root = root->left) v.push_back({root,root->right});
                } else {
                    ret.push_back(p.ROOT->val);
                    v.pop_back();
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

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