一、题目
1、原题链接
1497. 树的遍历
2、题目描述
一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的 层序遍历。
输入格式
第一行包含整数 N，表示二叉树的节点数。
第二行包含 N 个整数，表示二叉树的后序遍历。
第三行包含 N 个整数，表示二叉树的中序遍历。
输出格式
输出一行 N 个整数，表示二叉树的层序遍历。
数据范围
1≤N≤30,官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 1∼N。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
1
2
3
输出样例：
4 1 6 3 5 7 2
1
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
预备知识：
前序遍历：根左右（先遍历根结点，然后遍历左孩子、右孩子，下面类似）。
中序遍历：左根右。
后序遍历：左右根。
层次遍历：从根结点开始，依次从左往右遍历每层的结点。
（1）我们可以通过后序遍历的最后一个一个结点来确定整棵树的根结点，
（2）根据根结点的位置我们可以在中序遍历中得知整棵树的左右子树，分别包含哪些结点。
（3）递归地对左右子树进行上述操作，直到后序遍历中子树大小为空，这样就可以依次将每层的结点找到，然后把每层的结点记录下来，输出即可。
2、时间复杂度
时间复杂度O(n)
3、代码详解
用vector记录每层结点然后输出
#include <iostream>
#include <vector>
using namespace std;
const int N=35;
int n;
int h[N],z[N],p[N]; //h[]存储树的后序遍历，z[]存储树的中序遍历，p[i]存储值为i的数在中序遍历中的下标
vector<int> c[N]; //c[i]存储第i层的层序遍历
void build(int hl,int hr,int zl,int zr,int d){ //传入后序遍历的起点和终点、中序遍历的起点和终点,当前的层数
if(hl>hr) return ;
int val=h[hr]; //根结点的值
c[d].push_back(val); //将根结点加入第d层的层序遍历中
int idx=p[val]; //根结点在中序遍历中的下标
build(hl,hl+idx-1-zl,zl,idx-1,d+1); //递归遍历左子树
build(hl+idx-zl,hr-1,idx+1,zr,d+1); //递归遍历右子树
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>h[i];
}
for(int i=0;i<n;i++){
cin>>z[i];
}
for(int i=0;i<n;i++){
p[z[i]]=i;
}
build(0,n-1,0,n-1,0);
for(int i=0;i<n;i++){
for(int j=0;j<c[i].size();j++){
cout<<c[i][j]<<' ';
}
}
return 0;
}
建树，然后bfs输出层序遍历
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=35;
int n;
int h[N],z[N],p[N]; //h[]存储树的后序遍历，z[]存储树的中序遍历，p[i]存储值为i的数在中序遍历中的下标
int l[N],r[N]; //l[]存储每个结点的左孩子，r[]存储每个结点的右孩子
//建树，返回根结点
int build(int hl,int hr,int zl,int zr,int d){ //传入后序遍历的起点和终点、中序遍历的起点和终点,当前的层数
if(hl>hr) return 0; //如果子树为空，返回0
int val=h[hr]; //根结点的值
int idx=p[val]; //根结点在中序遍历中的下标
l[val]=build(hl,hl+idx-1-zl,zl,idx-1,d+1); //递归遍历左子树，找到左子树的根结点
r[val]=build(hl+idx-zl,hr-1,idx+1,zr,d+1); //递归遍历右子树，找到右子树的根结点
return val;
}
//bfs输出层序遍历
void bfs(){
queue<int> q;
q.push(h[n-1]);
while(q.size()){
int t=q.front();
q.pop();
cout<<t<<' ';
if(l[t]) q.push(l[t]);
if(r[t]) q.push(r[t]);
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>h[i];
}
for(int i=0;i<n;i++){
cin>>z[i];
}
for(int i=0;i<n;i++){
p[z[i]]=i;
}
build(0,n-1,0,n-1,0);
bfs();
return 0;
}
三、知识风暴
递归
递归是指函数直接或间接调用自己，是一种描述问题和解决问题的常用方法。
递归有两个基本要素：
边界条件：即确定递归到何时终止，也就是递归出口。
递归模式：即大问题是如何分解成小问题的，也就是递归体。
