Using a shadow stack to keep track of visited nodes


  • 0
    A

    // This is my first post for a solution, comments are welcome
    // Accepted solution - 0ms
    vector<int> postorderTraversal(TreeNode* root) {

        // main stack
        stack<TreeNode*> s;
    
        // shadow stack to track
        stack<int> t;
    
        vector<int> res;
        if(root == NULL)
            return res;
        s.push(root);
        t.push(0);
        while(!s.empty())
        {
            if(t.top() == 0 && s.top()->left !=NULL)
            {
                s.push(s.top()->left);
                // update value for the root node in shadow stack
                // 1 signifies visited left node
                t.pop();
                t.push(1);
                
                // 0 for the newly pushed node
                t.push(0);
            }
            else if(t.top()<2  && s.top()->right != NULL)
            {
                s.push(s.top()->right);
                t.pop();
                // 2 signifies we have also visited the right child
                t.push(2);
                t.push(0);
            }
            else
            {
                res.push_back(s.top()->val);
                // visited both children remove from main and shadow stack
                s.pop();
                t.pop();
            }
        }
        return res;
    }

Log in to reply
 

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