My concise C++ solution


  • 0
    S

    The basic idea is to use a stack to remember the pointer to a node and its right child, and the following code is self-explanatory.

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            if (!root) return {};
            vector<int> result;
            // pointer to a node and its right child
            stack<pair<TreeNode *, TreeNode*> >aStack;
            TreeNode *cur = root;
            
            // initialize the stack
            while (cur) {
                aStack.push(make_pair(cur, cur->right));
                cur = cur->left;
            }
            
            while (!aStack.empty()) {
                auto &aPair = aStack.top();
                if (!aPair.second) { // all left and right child tree has been visited
                    result.push_back(aPair.first->val);
                    aStack.pop();
                } else {
                    cur = aPair.second; // begin visit the right child tree
                    while (cur) {
                        aPair.second = nullptr; // mark that the right child tree is visited
                        aStack.push(make_pair(cur, cur->right));
                        cur = cur->left;
                    }
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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