今天一神给我手敲二叉树模板，瞬间就领悟了，感觉自己萌萌哒！
看上去很直观！
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e3+;
int a[maxn];
int b[maxn];
int floor[maxn];
int tr[maxn<<];
void build(int x,int al,int ar,int bl,int br) //和线段树差不多
{
if(ar<al||br<bl) return;
if(al==ar)
{
tr[x] = a[al];
return;
}
for(int i = al; i<=ar; i++)
{
if(a[i]==b[br])
{
tr[x] = b[br];
build( * x , al , i - , bl , bl + i - - al); //左子树的左端点，右端点，在a数组和b数组。
build( * x + , i + , ar , bl + i - al, br - ); //右子树的左端点，右端点，在a数组和b数组。
break;
}
}
}
/*void dfs(int x) //按先序遍历
{
if(!tr[x]) return;
printf("%d ",tr[x]);
dfs(2*x);
dfs(2*x+1);
}*/
void bfs(int x) //按层序遍历
{
queue<int> q;
q.push(x);
int ans = ;
while(!q.empty())
{
int y = q.front();
q.pop();
if(tr[y]==) continue;
floor[ans++] = tr[y];
q.push(*y);
q.push(*y+);
}
}
int main()
{
int n;
memset(tr,,sizeof(tr));
scanf("%d",&n);
for(int i = ; i<=n; i++)
{
scanf("%d",&b[i]);
}
for(int i = ; i<=n; i++)
{
scanf("%d",&a[i]);
}
build(,,n,,n);
//dfs(1);
bfs();
for(int i = ; i<n; i++) printf("%d ",floor[i]);
printf("%d\n",floor[n]);
return ;
}
只求先序时，不用遍历。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e3+;
int a[maxn];
int b[maxn];
vector<int> g;
void build(int x,int al,int ar,int bl,int br)
{
if(ar<al||br<bl) return;
if(al==ar)
{
g.push_back(a[al]);
return;
}
for(int i = al; i<=ar; i++)
{
if(a[i]==b[br])
{
g.push_back(a[i]);
build( * x , al , i - , bl , bl + i - - al);
build( * x + , i + , ar , bl + i - al, br - );
break;
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i = ; i<=n; i++)
{
scanf("%d",&b[i]);
}
for(int i = ; i<=n; i++)
{
scanf("%d",&a[i]);
}
build(,,n,,n);
for(int i = ; i<g.size()-; i++) printf("%d ",g[i]);
printf("%d\n",g[g.size()-1]);
return ;
}