Post order traversal using two satcks


  • 0
    C
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode *root) {
             stack<TreeNode*> s,out;
            vector<int> vec;
            if(root == NULL)
                return vec;
    
            s.push(root);
            while(!s.empty())
            {
                TreeNode* node = s.top();
                s.pop();
                out.push(node);
                if(node->left)
                    s.push(node->left);
                if(node->right)
                    s.push(node->right);
            }
    
            while(!out.empty())
            {
                vec.push_back(out.top()->val);
                out.pop();
            }
            return vec;
        }
    };

  • 1
    V

    One stack approach ..

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode *root) {
            stack<TreeNode *> st;
            vector<int> vRet;
            TreeNode *p, *pre = root;
    
            if (!root) return vRet;
            p = root->left;
            st.push(root);
            while (!st.empty() )
            {
                while (p) { st.push(p); p = p->left; }
                p = st.top();
                while (!p->right || pre==p->right)
                {
                    vRet.push_back(p->val);
                    pre = p;
                    st.pop();
                    if (st.empty() ) break;
                    p = st.top();
                }
                p = p->right;
            }
            return vRet;
        }
    } 

Log in to reply
 

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