/**

 * 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> result;

        if(root==nullptr) return result;

        stack<TreeNode*> s;

        TreeNode *p=root,*r=nullptr;

        while(p||!s.empty()){

            if(p){

                s.push(p);

                p=p->left;

            }else{

                p=s.top();

                if(p->right&&p->right!=r){

                    p=p->right;

                }else{

                    s.pop();

                    result.push_back(p->val);

                    r=p;

                    p=nullptr;

                }

                // if(p->right==nullptr||p->right==r){

                //     s.pop();

                //     result.push_back(p->val);

                //     r=p;

                //     p=nullptr;

                // }else{

                //     p=p->right;

                // }

            }

        }

        return result;

    }

};