One more C++ one-stack solution


  • 0
    Y

    Just remember if the node has been seen and append on the second time:

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode *root) {
            if (!root) {
                return {};
            }
            
            vector<int> res;
            using item = pair<TreeNode*, bool>;
            stack<item, vector<item>> work;
            work.push({root, false});
            while (!work.empty()) {
                auto& cur = work.top();
                if (cur.second) {
                    res.push_back(cur.first->val);
                    work.pop();
                } else {
                    cur.second = true;
                    auto node = cur.first;
                    if (node->right) {
                        work.push({node->right, false});
                    }
                    if (node->left) {
                        work.push({node->left, false});
                    }
                }
            }
            
            return res;
        }
    };

Log in to reply
 

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