/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

private:

    vector<int> nodeVec;

public:

    void traverse(TreeNode *root){

        if(root==NULL)

            return;

        traverse(root->left);

        traverse(root->right);

        nodeVec.push_back(root->val);

    }

    vector<int> postorderTraversal(TreeNode *root) {

        traverse(root);

        return nodeVec;

    }

};

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

private:

    vector<int> nodeVec;

public:void iterTraverse(TreeNode *root){

        if(root==NULL)

            return;

        stack<TreeNode*> st;

        TreeNode *pCur,*pPrev=NULL; //pCur: current tree node, pPrev: previous visited tree node

        st.push(root);

        while(!st.empty())

        {

            pCur=st.top();

            if((pCur->left == NULL && pCur->right == NULL) || (pPrev != NULL && (pCur->left==pPrev || pCur->right==pPrev)))

            {

                nodeVec.push_back(pCur->val);

                pPrev=pCur;

                st.pop();

            }

            else

            {

                if(pCur->right != NULL)

                    st.push(pCur->right);

                if(pCur->left != NULL)

                    st.push(pCur->left);

            }

        }

    }

    vector<int> postorderTraversal(TreeNode *root) {

        iterTraverse(root);

        return nodeVec;

    }

};