/*
题意：
1、push为先序，pop为后序，然后唯一确定一棵树
解题：
1、其实就是给先序和中序，求出后续
写法固定
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++) { //找到根节点
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;
}
//后续遍历
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;
}
