今日复习的知识点为递归。递归对于笔者而言是个比较难以理解的知识点，后续会多进行递归题目的练习。
AcWing1497.树的遍历
题目描述
一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。
输入格式
第一行包含整数 \(N\)，表示二叉树的节点数。
第二行包含 \(N\) 个整数，表示二叉树的后序遍历。
第三行包含 \(N\) 个整数，表示二叉树的中序遍历。
输出格式
输出一行 \(N\) 个整数，表示二叉树的层序遍历。
数据范围
\(1≤N≤30,\)
官方(PAT)并未给出各节点权值的取值范围，为方便起见，在本网站(AcWing)范围取为 \(1∼N\)。
输入样例
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例
4 1 6 3 5 7 2
解题思路
首先我们要根据后序和中序遍历来将这棵树建立起来。那么以样例为例，具体的建树流程如下(假定读者已知树的后序和中序遍历)：
由后序遍历，根节点是最后输出的，故 \(4\) 为根节点。而在中序遍历中，先遍历左子树，后遍历根，最后遍历右子树，那么在中序遍历的序列中，\(4\) 的左部为左子树的所有节点，右部为右子树的所有节点。在后序遍历中，先遍历左子树，后遍历右子树，最后是根节点，那么我们根据中序遍历中左右子树的节点数量就可以确定其左右子树在后序遍历序列中的位置。然后对于左右子树我们采取相同的措施完成建树。也就是一个大问题分解为了若干小问题，而小问题的求解思路和整个问题的求解思路相同。在建树过程中存一下对应层的节点。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int n;
int post[N], in[N];
int pos[N];
vector<int> level[N];
void build(int pl, int pr, int il, int ir, int d)
{
if (pl > pr) return;
int val = post[pr];
level[d].push_back(val);
int k = pos[val];
build(pl, pl + k - 1 - il, il, k - 1, d + 1);
build(pl + k - il, pr - 1, k + 1, ir, d + 1);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++) cin >> post[i];
for (int i = 0; i < n; i ++) cin >> in[i];
for (int i = 0; i < n; i ++) pos[in[i]] = i;
build(0, n - 1, 0, n - 1, 0);
for (int i = 0; i < n; i ++)
for (auto x: level[i])
cout << x << ' ';
return 0;
}
二叉树
一个二叉树，树中每个节点的权值互不相同。在二叉树中，给定中序遍历和另外一种遍历(先序、后序以及层序遍历)就可以构建一颗唯一的二叉树。前面的题目是根据中序和后序建树。我们接下来介绍另外两种。
中序遍历+先序遍历
思路类似。先序遍历是先遍历根节点，然后左子树，最后右子树，那么我们可以直接确定根节点，也就是先序遍历的第一个元素。建树的话，可以额外开两个数组 l[N] 和 r[N] 来记录左右节点。具体代码类似前面的，建树时可以不考虑层数这一参数。
中序遍历+层序遍历
层序遍历是按层输出节点。那么层序遍历序列的第一个元素就是根节点，那么我们就可以在中序遍历中确定其左右子树。
int build(int il, int ir) //##核心函数：传入中序，递归实现寻找每个节点的左右孩子
{
int root, k;
for (int i = 1;i <= n; i ++){ //中序数列il到ir位置的数中，第一个在层序数列中出现的就是根节点
if (mp[floor[i]] >= il && mp[floor[i]] <= ir){ // mp存放节点在中序的位置
root = floor[i];
break;
}
}
k = mp[root];
//k>il，根节点左边有位置，说明有左子树
if (k > il) a[root].l = build(il, k - 1); //中序数列中根节点root位置左边的是左子树
if (k < ir) a[root].r = build(k + 1, ir);
return root; //返回的是根节点！（作为其父树的左孩子或者右孩子）
}