```
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
stack<TreeNode*> s;
while (root){
s.push(root);
if (root->left) root = root->left;
else root = root->right;
}
while (s.size()){
// Top of stack s is the next one to iterate.
TreeNode* p = s.top(); s.pop();
ret.push_back(p->val);
// If p is the root of the input tree, it would be empty.
if (s.empty()){
break;
}
TreeNode* rt = s.top(); s.pop();
// p is the right child, or there is no right child for p's father.
if (!rt->right || p==rt->right) { s.push(rt); continue;}
// p is the left child
else{
while (rt){
s.push(rt);
// Avoid of adding p itself back into stack s
if (p!=rt->left && rt->left) rt = rt->left;
else if(p!=rt->right && rt->right) rt = rt->right;
else {rt=NULL;}
}
}
}
return ret;
}
};
```