原题干：
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop
Sample Output:
3 4 2 6 5 1
生词：
implemented：执行，实现 non-recursive：非递归
题目大意：
使用堆栈模拟二叉树的遍历，（其实给出的就是二叉树的前序和中序遍历），输出二叉树后序遍历结果。
感觉变量名写的很明白了，就不加注释了。有不懂的同学直接在下面评论或者发邮件吧。看到了会回复的。
代码：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int> pre, in, post;
struct node{
int n;
node *lchild, *rchild;
};
node* BuildTree(int preL, int preR, int inL, int inR){
if(inL > inR || preL > preR) return NULL;
int _root = pre[preL];
node *root = new node;
root->n = _root;
int root_pos = find(in.begin(), in.end(), _root) - in.begin();
int lchild_len = root_pos - inL;
int _L_preL = preL + 1,
_L_preR = lchild_len + preL,
_L_inL = inL,
_L_inR = root_pos - 1;
root->lchild = BuildTree(_L_preL, _L_preR, _L_inL, _L_inR);
int _R_preL = _L_preR + 1,
_R_preR = preR,
_R_inL = root_pos + 1,
_R_inR = inR;
root->rchild = BuildTree(_R_preL, _R_preR, _R_inL, _R_inR);
return root;
}
void dfs(node *root){
if(!root) return;
dfs(root->lchild);
dfs(root->rchild);
post.push_back(root->n);
}
int main(){
int cnt;
cin >> cnt;
stack<int> S;
do{
string cmd;
cin >> cmd;
if(cmd == "Push"){
int n;
cin >> n;
S.push(n);
pre.push_back(n);
}
else { //pop
in.push_back(S.top());
S.pop();
}
}while(in.size() != cnt || pre.size() != cnt);
node *T = BuildTree(0, cnt - 1, 0, cnt - 1);
dfs(T);
for(int i = 0; i < post.size(); i++){
if(i) cout << ' ';
cout << post[i];
}
cout << endl;
return 0;
}