class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        while(root){
            ans.push_back(root->val);
            if(!root->right){
                root= root->left;
            }
            else{
                TreeNode* next = root->right;
                if(!next->left){
                    next->left = root->left;
                    root = next;
                }
                else{
                    while(next->left){
                        next = next->left;
                    }
                    next->left = root->left;
                    root = root->right;
                }
            }
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};