Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.2 kB
1
Indexable
Never
    /*
        Approach 1 - Do preorder traversal with (root, right, left) and then reverse the final output array.
    */


    /*
        Approach 2 - Push a node two times in stack.
        The first time its poped means LST is covered (curr == st.top())
        The second time its poped means LST and RST both covered so now print the root.
    */
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode *curr = root;
        stack<TreeNode *> st;
        vector<int> res;

        while (!st.empty() || curr != NULL) {
            if (curr != NULL) {
                st.push(curr); // Push a node 2 times in stack.
                st.push(curr);
                curr = curr -> left;
            } else {
                curr = st.top();
                st.pop();
                if (st.size() > 0 && curr == st.top()) // It means LST is covered now go to RST.
                    curr = curr -> right;
                else { // It means LST and RST both covered so now print the root.
                    res.push_back(curr -> val);
                    curr = NULL;
                }
            }
        }

        return res;
    }