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> ret;
        if (root == NULL)
            return ret;
        TreeNode *p = root;
        stack<TreeNode *> toTraversal;
        TreeNode *last = root;
        toTraversal.push(p);
        while (!toTraversal.empty())
        {
            p = toTraversal.top();
            if ((p->left == NULL && p->right == NULL) || (p->right == NULL && last == p->left) || (last == p->right))
            {
                ret.push_back(p->val);
                last = p;
                toTraversal.pop();
            }
            else
            {
                if (p->right)
                    toTraversal.push(p->right);
                if (p->left)
                    toTraversal.push(p->left);
            }
        }

        return ret;
    }
};