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].

使用两个栈

/**
 * 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) {
        vector<int> res;

        if(root != NULL){
            stack<TreeNode *>   st1;
            stack<TreeNode *>   st2;
            st1.push(root);

            while(!st1.empty()){
                root = st1.top();
                st1.pop();
                st2.push(root);

                if(root->left)  st1.push(root->left);
                if(root->right) st1.push(root->right);
            }

            while(!st2.empty()){
                res.push_back(st2.top()->val);
                st2.pop();
            }
        }
        return res;
    }
};

只使用一个栈

/**
 * 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) {
        vector<int> res;
        TreeNode *h;
        if(h = root){
            stack<TreeNode *>   st;
            st.push(root);
            TreeNode *c = NULL;

            while(!st.empty()){
                c = st.top();

                if(c->left != NULL && c->left != h && c->right != h){
                    st.push(c->left);
                }else if(c->right != NULL && c->right != h){
                    st.push(c->right);
                }else{
                    res.push_back(c->val);
                    st.pop();
                    h = c;
                }
            }
        }
        return res;
    }
};