Binary Tree Postorder Traversal [Leetcode]

In the previous post, we did the binary tree preorder traversal without using recursion. I find its solution can be modified a little bit to achieve postorder traversal. The idea is the similar, the only difference is that we push the left child first instead of pushing right child first.

1. Push the root into stack;
2. Do the follwoing steps until the stack is empty:
• Pop out the top-most node in the stack as the current node; and add it in the front of the resulting vector (or push it into another stack and then pop it out before all nodes are pushed in the the stack);
• Push its left child and then right child into stack if they exist.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> ret;
        if(root==NULL)
            return ret;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            st.pop();
            ret.insert(ret.begin(), cur->val);
            if(cur->left!=NULL)
                st.push(cur->left);
            if(cur->right!=NULL)
                st.push(cur->right);
        }
        return ret;
    }
};

The solution above actually needs two stacks if we want to print on the fly. The following is the solution using only one stack. The basic idea is to traverse the tree in the depth first fashion; print the node if (1) all its children have been traversed or (2) it has no children. To indicate the direction of traversing (down or up), we use a pointer pre to denote the previously-traversed node, and a pointer cur to denote the node we are traversing right now. [click here for more details; see here for another good solution]

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> ret;
        if(root==NULL)
            return ret;
        stack<TreeNode*> st;
        TreeNode* pre = NULL;
        TreeNode* cur = NULL;
        st.push(root);
        while(!st.empty()){
            //Traversing down the tree
            cur = st.top();
            if(pre==NULL || cur==pre->left || cur==pre->right){
                if(cur->left!=NULL)
                    st.push(cur->left);
                else if(cur->right!=NULL)
                    st.push(cur->right);
                else
                {
                    ret.push_back(cur->val);
                    st.pop();
                }
            }
            //Traversing up the tree from left
            else if(cur->left==pre){
                if(cur->right!=NULL)
                    st.push(cur->right);
                else{
                    ret.push_back(cur->val);
                    st.pop();
                }
            }                
            //Traversing up the tree from right
            else if(cur->right==pre){
                    ret.push_back(cur->val);
                    st.pop();
            }
            //Keep track of the previously traversed node
            pre = cur;
        }
        return ret;
    }
};