《非常简单的一道题目》
就，如果你懂得关于树的知识，那么就确实就是很简单。题目都没有很难的，你觉得难是因为你的知识点不熟练。
满分代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+10;
int in[N],pre[N],n;
struct Node{
int l,r;
}Tree[N];
int build(int l1,int r1,int l2,int r2){//l1-r1中序遍历，l2-r2先序遍历
if(l1 > r1 || l2 > r2) return 0;
int p = l1;
while(in[p] != pre[l2]) p++;
int len = p - l1;
int rt = pre[l2];
Tree[rt].l = build(l1,p-1,l2+1,l2 + len);
Tree[rt].r = build(p+1,r1,l2+len+1,r2);
return rt;
}
vector<int> ans;
void bfs(int s){
queue<int> que;
que.push(s);
while(!que.empty()){
int rt = que.front();
que.pop();
ans.push_back(rt);
int l = Tree[rt].l,r = Tree[rt].r;
if(r) que.push(r);
if(l) que.push(l);
}
}
int main()
{
cin>>n;
for(int i = 1;i <= n; ++i) cin>>in[i];
for(int i = 1;i <= n; ++i) cin>>pre[i];
build(1,n,1,n);
bfs(pre[1]);
for(int i=0;i<ans.size();i++){
cout<<ans[i];
if(i!=ans.size()-1)cout<<" ";
}
return 0;
}
建树
建树就非常简单，就用结构体，一个l一个r就好了。
建树的思路：
1.先在中序中找到你当前树的根
int p = l1;
while(in[p] != pre[l2]) p++;
当前树指的是你当前树，因为之后可能会进入子树，那么当前树就变成了那个子树
而这个根已经给出来了，其实就是你当前树的先序序列的第一个
2.求出左子树的长度
其实就是int len = p - l1
3.当前根的左孩子和右孩子递归求解
这里的参数呢，这四个分别是：
当前的
中序的第一个索引，中序的最后一个索引，先序的第一个索引，先序的最后一个索引
int rt = pre[l2];
Tree[rt].l = build(l1,p-1,l2+1,l2 + len);
Tree[rt].r = build(p+1,r1,l2+len+1,r2);
return rt;
4.特判，如果说你当前树递归下去发现了不合法（左大于右）那么就说明它不应该递归下去。它是一个叶子结点。
if(l1 > r1 || l2 > r2) return 0;
代码
int build(int l1,int r1,int l2,int r2){//l1-r1中序遍历，l2-r2先序遍历
if(l1 > r1 || l2 > r2) return 0;
int p = l1;
while(in[p] != pre[l2]) p++;
int len = p - l1;
int rt = pre[l2];
Tree[rt].l = build(l1,p-1,l2+1,l2 + len);
Tree[rt].r = build(p+1,r1,l2+len+1,r2);
return rt;
}
层序遍历（用bfs）
就是说你要求层序遍历。最后的方法，正解，就是bfs。因为bfs好像从定义来看，就是一层一层地。其实就是完完全全的层序遍历的定义啊。
思路：
反正你的树已经建好了嘛。
那么你先把根放进去
之后按照先右结点再左结点的顺序去push进去
按照这个顺序去bfs就好了。
（注意，因为上面设置了叶子结点的左右都是0，所以你需要判断一下，如果是0的话，说明是叶子结点，那就不用放进去了）
代码
void bfs(int s){
queue<int> que;
que.push(s);
while(!que.empty()){
int rt = que.front();
que.pop();
ans.push_back(rt);
int l = Tree[rt].l,r = Tree[rt].r;
if(r) que.push(r);
if(l) que.push(l);
}
}
