a rather understandable solution in C++


  • 0
    H

    The key idea is to not only push the current node to the stack,
    but also the state that represents which the next node to visit(including 3 states:0,myself; 1,left; 2,right).

    struct InfoCall{
    TreeNode* node;
    // 0:myself, 1:left, 2:right
    int toVisit;
    InfoCall(TreeNode* curNode) : node(curNode), toVisit(1) {}
    };
    class Solution {
    public:
    vector<int> postorderTraversal(TreeNode* root) {
    vector<int> seq;
    if (root == nullptr)
    return seq;

        stack<InfoCall> stackCall;
        stackCall.push(InfoCall(root));
        while (!stackCall.empty())
        {
            InfoCall& call = stackCall.top();
            int& toVisit = call.toVisit;
            switch (toVisit)
            {
                case 1:
                    toVisit = 2;
                    if (call.node -> left)
                        stackCall.push(InfoCall(call.node -> left));
                    break;
                case 2:
                    toVisit = 0;
                    if (call.node -> right)
                        stackCall.push(InfoCall(call.node -> right));
                    break;
                case 0:
                    seq.push_back(call.node -> val);
                    stackCall.pop();
            }
        }
        return seq;
    }
    

    };
    '''


Log in to reply
 

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