题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805069361299456
L2-006 树的遍历 （25 分)
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2解题思路：首先我们根据后序遍历最后一个数可确定二叉树的根，然后再从中序遍历找到该节点便能确定该根节点左右子树的节点，举个例子拿样例来说：
初始时，我们根据后序遍历知道整棵树的根节点是4，于是我们便在中序遍历找到4的位置，我们就可以确定，节点1，2，3在根节点左子树，节点3，5，7，2在根节点右子树，于是我们又采用此方法，递归在后序遍历的区间【1，3】和中序遍历的区间【1，3】建立4的左子树，在后序遍历的区间【4，6】和中序遍历的区间【5，7】建立4的右子树就可以了。
具体方法看代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,post[],mid[];
struct node{
int l,r;
}tree[];
vector<int> ans;
int build(int l1,int r1,int l2,int r2){//l1,r1表示中序遍历的左右边间,l2,r2表示后序遍历的左右边界
if(l1>r1)return ; //递归结束条件即没有元素可以遍历
int p1,cnt,rt=post[r2]; //rt为当前子树的根节点 即为当前后序遍历的最后一个数
p1=l1; //初始p1位中序遍历的左边界
while(mid[p1]!=rt)p1++; //在中序遍历中查找根节点所在位置
cnt=p1-l1; //计算当前根节点的子节点个数
tree[rt].l=build(l1,p1-,l2,l2+cnt-); //递归构建左子树
tree[rt].r=build(p1+,r1,l2+cnt,r2-); //递归构建右子树
return rt;
}
void bfs(int rt){ //bfs搜索层序遍历
queue<int> que;
que.push(rt);
ans.push_back(rt);
while(que.size()){
int u=que.front();
que.pop();
if(tree[u].l!=){
que.push(tree[u].l);
ans.push_back(tree[u].l);
}
if(tree[u].r!=){
que.push(tree[u].r);
ans.push_back(tree[u].r);
}
}
for(int i=;i<ans.size();i++){
cout<<ans[i];
if(i!=ans.size()-)cout<<" ";
else cout<<endl;
}
}
int main(){
cin>>n;
for(int i=;i<=n;i++)cin>>post[i];
for(int i=;i<=n;i++)cin>>mid[i];
int root=build(,n,,n);
bfs(root);
return ;
}
L2-011 玩转二叉树 （25 分)
题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805065406070784
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
输出样例：
4 6 1 7 5 3 2解题思路：和上题几乎是一样的，把后序改为先序，先序遍历的第一个元素就是根节点，知道这个就可以了。镜面反转只需要改变一下bfs的搜索方式就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,root,pre[],mid[];
struct node{
int l,r;
}tree[];
vector<int> ans;
int build(int l1,int r1,int l2,int r2){//l1,r1为中序遍历的左右边界,l2,r2为先序遍历的左右边界
if(l1>r1)return ;
int p,cnt,rt=pre[l2]; //先序遍历的第一个元素为当前树的树根
p=l1;
while(mid[p]!=rt)p++;
cnt=p-l1;
tree[rt].l=build(l1,p-,l2+,l2+cnt);
tree[rt].r=build(p+,r1,l2+cnt+,r2);
return rt;
}
void bfs(int rt){
queue<int> que;
que.push(rt);
ans.push_back(rt);
while(que.size()){
int u=que.front();
que.pop();
if(tree[u].r!=){
ans.push_back(tree[u].r);
que.push(tree[u].r);
}
if(tree[u].l!=){
ans.push_back(tree[u].l);
que.push(tree[u].l);
}
}
for(int i=;i<ans.size();i++){
cout<<ans[i];
if(i!=ans.size()-)cout<<" ";
else cout<<endl;
}
}
int main(){
cin>>n;
for(int i=;i<=n;i++)cin>>mid[i];
for(int i=;i<=n;i++)cin>>pre[i];
root=build(,n,,n);
bfs(root);
return ;
}