/*
題意：
1兔毙、push為先序柠辞，pop為后序尘颓，然后唯一確定一棵樹
解題：
1走触、其實就是給先序和中序，求出后續(xù)
寫法固定
learn && wrong:
1疤苹、格式不對
*/
#include <iostream>
#include <queue>
#include <cstring>
#include <stack>
using namespace std;
/*
1互广、結構體
2、合成樹
3卧土、后序遍歷
*/
const int maxn = 50;
int preorder[maxn], inorder[maxn],postorder[maxn];
int n;
struct node {
int data;
node* lchild;
node* rchild;
};
node* create(int preL, int preR, int inL, int inR) {
if (inL > inR) { //遞歸邊界
return NULL;
}
node* root = new node;
root->data = preorder[preL];
int i;
for (i = inL;i < inR;i++) { //找到根節(jié)點
if (inorder[i] == preorder[preL]) { //!!!又是preL這里錯
break;
}
}
int leftnum = i - inL ; // １怪濉！尤莺！
//先序的左子樹 preL + 1,preL + leftnum, 中序inL, inL + i - 1
root->lchild = create(preL + 1, preL + leftnum, inL, i - 1);
//先序的右子樹 preL + leftnum + 1,preR, 中序 i + 1旅敷，
root->rchild = create(preL + leftnum + 1, preR, i + 1, inR);
return root;
}
//后續(xù)遍歷
int num = 0;
void post(node* root) {
if (root == NULL) {
return;
}
post(root->lchild);
post(root->rchild);
printf("%d", root->data);
num++; //！２媳谁！順序顛倒
if (num < n) {
printf(" ");
}
}
int main()
{
cin >> n;
char str[5];
stack<int> st;
int x, preindex = 0, inindex = 0; //入棧元素涂滴，先序序列位置及中序序列位置
for (int i = 0;i < 2 * n;i++) {
cin >> str;
if (strcmp(str, "Push") == 0) {
cin >> x;
preorder[preindex++] = x;
st.push(x);
}
else {
inorder[inindex++] = st.top();
st.pop();
}
}
node* root = create(0, n - 1, 0, n - 1);
post(root);
return 0;
}
