作者：指针不指南吗
专栏：Acwing 蓝桥集训每日一题

🐾或许会很慢，但是不可以停下来🐾

文章目录

• 1.树的遍历
• 2.递归实现排列型枚举
• 3.递归求阶乘
• 4.求斐波那契数列

1.树的遍历

一个二叉树，树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

输入格式

第一行包含整数 N，表示二叉树的节点数。

第二行包含 N 个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式

输出一行 N 个整数，表示二叉树的层序遍历。

数据范围

1≤N≤30，
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 1∼N。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

1. 知识点

• 层序遍历：从上往下，从左往右一层一层遍历；

• 中序遍历：先遍历左节点，再遍历根节点，最后遍历右节点；

• 前序遍历：先遍历根节点，再遍历左节点，最后遍历右节点；

• 后序遍历： 先遍历左节点，再遍历右节点，最后遍历根节点；

  

2. 推导树的原型过程

​ (1) 首先根据后序遍历的最后一个数，来确定根节点，在中序遍历中找到相同的数即根节点；

​ (2) 由根节点在中序遍历中的位置，我们可以推出来，左子树长度，右子树长度，对应的在后序遍历中找到；

​ (3) 再根据后序遍历中左子树的最后一个，即左子树的根节点，…，递归

• 最后需要层序遍历：

  我们可以先开一个vector，第一层放在 vector[ 0 ] 里面，第二层放在vector[1]里面…

3. 代码实现

   #include
   using namespace std;const int N=35;
   int a[N],b[N],p[N];  
   int n;vector level[N]; //每一层用一个vector来存数值,因为我们要层序遍历输出；void build(int al,int ar,int bl,int br,int d) //d表示树的层数；
   {if(al>ar) return ;   // 当al>ar时，说明，已经递归到最后一个子树；int val=a[ar];  //每个子树的根节点就是后续遍历的最后一个数字，用val存下来；level[d].push_back(val);  //把每个根节点都存在 对应每一层的数组中去，用于层序遍历输出；int k=p[val];  //k来表示根节点在中序遍历中的位置；build(al,k-1-bl+al ,bl,k-1,d+1);  //递归左子树,下一层d+1;build(k-bl+al,ar-1,k+1,br,d+1);   //递归右子树
   }int main()
   {cin>>n;for(int i=0;i>a[i];  //a表示后序遍历；for(int i=0;i>b[i];  //b表示中序遍历;for(int i=0;i

   补充

   build的函数参数的表示如下图:

   后序遍历中左子树的ar 的计算,列个方程即可,如下图:

   

#include
using namespace std;const int N=10;int n;
int st[N];   //表示每个位置上填的数是多少 1~n;
bool used[N];  //表示这个数有没有用过，false表示没用过，true表示用过void f(int u)  //u表示位置，函数的功能是 给第 u 个位置上排上数
{if(u>n){  //表示已经排到最后一位，即边界for(int i=1;i<=n;i++)  printf("%d ",st[i]) ; //这时候i表示位置，输出每个位置上的数，即输出一种方案puts("") ;return ;}//枚举当前位置上可以填哪些数for(int i=1;i<=n;i++){  // 这时候 i 表示在u的位置上所填的数；按照字典顺序小的在前面，设置循环，从 1开始依次往下排if(!used[i]) {  //如果这个这个数没有用过，则把这个数排在 此时 u 的位置上st[u]=i;used[i]=true;f(u+1);  //排下一个位置，递归更深一层！！//重点解析：递归在更深层是在上一层的基础上递归的，即如果上一层已经用过2了，那下一层就不能用了，遇到边界，开始返回上一层st[u]=0;  //恢复现场，供下一次使用used[i]=false;  }}int main()
{cin>>n;f(1);  //从第一个位置上开始排return 0;
}