Iterative Postorder Traversal by Visiting Right Subtree First (C++, 2 stacks, 1 vector)


  • 0
    F
    vector<int> postorderTraversal(TreeNode *root) {
        TreeNode *p = NULL;       // auxiliar pointer points to the tree root
        stack<int> elements;      // keep track of the elements in to maintain postorder
        stack<TreeNode *> visits; // keeps track of elements being visited in the BST
        vector<int> postorder;    // store and allow visit elements in postorder
        
        // push root node onto the visit stack
        if (root) visits.push(root);
        while (!visits.empty()) {
            // visit element in the top of stack
            p = visits.top();
            // store element in postorder
            elements.push(p->val);
            // if there exists a right subtree, visit it first
            if (p->right != NULL) {
                visits.push(p->right);
            } else { // if not
                visits.pop();
                // visit the left subtree
                if (p->left != NULL) {
                    visits.push(p->left);
                } else {
                    // backtrack if needed
                    while (!visits.empty()) {
                        p = visits.top();
                        visits.pop();
                        // if a left non-empty subtree is found, visit it
                        if (p->left != NULL) {
                            visits.push(p->left);
                            break;
                        }
                        // else check if the element on the top of the stack can
                    }
                }
            }
        }   
    
        // store elements in postorder into an array
        while (!elements.empty()) {
            postorder.push_back(elements.top());
            elements.pop();
        } 
    
        return postorder;
    }

Log in to reply
 

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