Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Use two stacks to simulate recursion.

stack st stores visiting nodes, stack si stores visiting values.

//I should use a stack to simulate recursion

/**
 * Definition for a binary tree node.
 * 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) {
        //extreme case
        if(root == NULL) return vector<int>();
        //ordinary case
        stack<TreeNode *> st;
        stack<int> si;
        vector<int> re;
        st.push(root);
        while(!st.empty()){
            TreeNode * node = st.top();
            st.pop();
            si.push(node->val);
            if(node->left) st.push(node->left); // push left first, access left last
            if(node->right) st.push(node->right);// Remember, the pre-order traversal sequence is not the reverse of post-order traversal. 
           
        }
        while(!si.empty()){
            re.push_back(si.top());
            si.pop();
        }
        return re;
    }
};