> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/solutions/binary_tree_postorder_traversal/stack.md).

# //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);

}

};