//stack

vector<int> postorderTraversal(TreeNode* root) {

stack<TreeNode*> s;

vector<int> ret;

TreeNode q=nullptr, p=root;

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

if(p){

s.push(p);

p=p->left;

}else{

p=s.top();

if(p->right&&p->right!=q){ //右子未访问 所以不但当前P不弹出 而且将P右子塞入（左子已经访问完？）然后从右子的左子树继续（设为新P）

p=p->right;

s.push(p);

p=p->left;

}else{

ret.push_back(p->val);

q=p;

s.pop();

p=nullptr;

}

}

}

return ret;

}

//morris 没过！！！！！

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

TreeNode dummy(-1);

TreeNode p, temp;

vector<int> result;

stringstream out;

p=&dummy;

p->left=root;

while(p){

temp=p->left;

if(!temp){

p=p->right;

}else{

while(temp->right && temp->right!=p)

temp=temp->right;

if(!temp){

temp->right=p;

p=p->left;

}else{

reversePrint(p->left,temp,result);

if(result.size()>0 )

break;

temp->right=nullptr;

p=p->right;

}

}

}

return result;

}

void reverse(TreeNode from, TreeNode to){

if(from==to) return;

TreeNode x=from, y=x->right, *z;

while(x!=to){

z=y->right;

y->right=x;

x=y;

y=z;

}

}

void reversePrint(TreeNode from, TreeNode to, vector<int> &ret ){

reverse(from,to);

TreeNode *p=to;

while(true){

ret.push_back(p->val);

if(p==from)

break;

p=p->right;

}

reverse(to,from);

}

};