C++ no reverse solution with explanations


  • 1
    V
    vector<int> postorderTraversal(TreeNode* root) {
        
        vector<int> result;
        
        stack<TreeNode*> nodeStack;
        TreeNode* lastVisited = nullptr;
        while(!nodeStack.empty() || root != nullptr)
        {
            if(root != nullptr) 
            {
                // push on stack and go to the left
                nodeStack.push(root);
                root = root->left;
            }
            else
            {
                TreeNode* node = nodeStack.top();
                if(node->right == nullptr || node->right == lastVisited)
                {
                    // if the right node was allready visited
                    // visit it and pop from the stack
                    result.push_back(node->val);
                    lastVisited = node;
                    nodeStack.pop();
                }
                else // go to the right
                    root = node->right;
            }
        }
        
        return result;
    }

Log in to reply
 

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