C++ 10-12 lines iterative solution for Postorder, Preorder and Inorder traversal


  • 0

    Big idea is to use a stack to record nodes to be processed.

    Postorder:
    Keep track of last processed node to indicate if current node is ready to be processed.

    vector<int> postorderTraversal(TreeNode* root) {
            vector<int> ans;
            stack<TreeNode*> st;
            if (root) { st.push(root); }
            
            // ensure last won't match root's left/right children
            for (TreeNode *last = root, *cur; st.size() && (cur = st.top());) {
                if ((!cur->left && !cur->right) || (cur->left == last && !cur->right) || (cur->right == last)) {
                    ans.push_back((last = cur)->val); st.pop();     // it's cur's turn to get recorded
                } else {
                    if (cur->right) { st.push(cur->right); }
                    if (cur->left) { st.push(cur->left); }
                }
            }
            
            return ans;
    }
    

    Preorder:

    vector<int> preorderTraversal(TreeNode* root) {
            vector<int> ans;
            stack<TreeNode*> st;
            if (root) { st.push(root); }
            
            while (st.size()) {
                TreeNode* cur = st.top(); st.pop();             // process current node
                ans.push_back(cur->val);                        // record node value
                if (cur->right) { st.push(cur->right); }
                if (cur->left) { st.push(cur->left); }
            }
            
            return ans;
    }
    

    Inorder:
    Always put leftmost node to process on top of the stack.

    class Solution {
    private:
        stack<TreeNode*> st;
        
        void update(TreeNode* cur) {
            for (; cur; cur = cur->left) { 
                st.push(cur);                               // pushing left node into stack all the way
            }
        }
        
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> ans;
            update(root);                                   // add root in stack
            
            for (TreeNode* cur; st.size() && (cur = st.top()); st.pop(), update(cur->right)) {
                ans.push_back(cur->val);                    // record leftmost value and add candidate right node in stack
            }
            
            return ans;
        }
    };
    

Log in to reply
 

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