注释部分是使用vector 实现stack 的功能，但是最后一个测试点错误，不明原因。
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int maxn = 31;
struct node{int data;node* lchild;node* rchild;
};
//vector<int> pre, in, temp;
int pre[maxn], in[maxn];
node* create(int preL, int preR, int inL, int inR){if(preL > preR) return NULL;node* root = new node;root->data = pre[preL];int k;for(k = inL; k < inR; k++)if(in[k] == pre[preL]) break;int numLeft = k - inL;root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);root->rchild = create(preL + numLeft + 1, preR, k + 1, inR);return root;
}
int n, num = 0;
void postorder(node* root){if(root == NULL) return;postorder(root->lchild);postorder(root->rchild);printf("%d", root->data);num++;if(num < n) printf(" ");
}
int main(){string s;scanf("%d", &n); getchar();// for(int i = 0; i < 2*n; i++){// getline(cin, s);// if(s.length() > 4){// pre.push_back(s[5] - '0'); temp.push_back(s[5] - '0');// }else{// in.push_back(temp[temp.size() - 1]); temp.pop_back();// }// }int x, preindex = 0, inindex = 0;stack<int> st;for(int i = 0; i < 2*n; i++){cin >> s;if(s == "Push"){cin >> x; pre[preindex++] = x;st.push(x);}else{in[inindex++] = st.top();st.pop();}}node* root = create(0, n - 1, 0, n - 1);postorder(root);return 0;
}