/**

 * 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) {

        vector<int>result;

        TreeNode*node=root;

        stack<TreeNode*>st;

        stack<bool>st_flag;

        while(node){

            st.push(node);

            st_flag.push(false);

            node=node->left;

        }

        while(!st.empty()){

            bool status = st_flag.top();

            if(!status){

                //訪问右子树

                st_flag.pop(); st_flag.push(true);

                node = st.top();

                node=node->right;

                while(node){

                    st.push(node);

                    st_flag.push(false);

                    node=node->left;

                }

            }

            else{

                //訪问当前结点

                st_flag.pop();

                node = st.top(); st.pop();

                result.push_back(node->val);

            }

        }

        return result;

    }

};