#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
static const int N=31;
int pre[N],in[N];
TreeNode* create(int len,int *pre,int *in)
{
int i;
TreeNode *root;
if(len<=0)return nullptr;
root=new TreeNode(pre[0]);
for(i=0;i<len;i++)
{
if(in[i]==root->val)break;
}
root->left=create(i,pre+1,in);
root->right=create(len-i-1,pre+i+1,in+i+1);
return root;
}
vector<TreeNode*>getBinaryTrees(vector<int>&preOrder,vector<int>inOrder)
{
int n=preOrder.size(),m=inOrder.size();
for(int i=0;i<n;i++)pre[i]=preOrder[i],cout<<pre[i]<<' ';
cout<<endl;
for(int i=0;i<m;i++)in[i]=inOrder[i],cout<<in[i]<<' ';
cout<<endl;
TreeNode *T=create(n,pre,in);
vector<TreeNode*>v;
queue<TreeNode*>q;
q.push(T);
int cnt=0;
while(q.size())
{
int sz=q.size();
for(int i=0;i<max(sz,(int)pow(2,cnt));i++)
{
if(i<sz)
{
auto t=q.front();
q.pop();
v.push_back(t);
if(t->left)q.push(t->left);
else v.push_back(new TreeNode(-1));
if(t->right)q.push(t->right);
else v.push_back(new TreeNode(-1));
}
else v.push_back(new TreeNode(-1));
}
cnt++;
}
return v;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
//while(_--)solve();
vector<int>v1,v2;
v1.push_back(1),v1.push_back(1),v1.push_back(2);
v2.push_back(1),v2.push_back(2),v2.push_back(1);
vector<TreeNode*>v=getBinaryTrees(v1,v2);
for(auto x:v)cout<<x->val<<' ';
cout<<endl;
return 0;
}