掌握商务网站建设内容,游戏推广怎么快速拉人,江门骏域网站建设,软件平台开发公司作者#xff1a;指针不指南吗 专栏#xff1a;Acwing 蓝桥集训每日一题 #x1f43e;或许会很慢#xff0c;但是不可以停下来#x1f43e; 文章目录1.树的遍历2.递归求阶乘3.求斐波那契数列1.树的遍历 一个二叉树#xff0c;树中每个节点的权值互不相同。 现在给出它的后… 作者指针不指南吗 专栏Acwing 蓝桥集训每日一题 或许会很慢但是不可以停下来 文章目录1.树的遍历2.递归求阶乘3.求斐波那契数列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) 由根节点在中序遍历中的位置我们可以推出来左子树长度右子树长度对应的在后序遍历中找到
(3) 再根据后序遍历中左子树的最后一个即左子树的根节点…递归 最后需要层序遍历 我们可以先开一个vector第一层放在 vector[ 0 ] 里面第二层放在vector[1]里面… 代码实现 #includebits/stdc.h
using namespace std;const int N35;
int a[N],b[N],p[N];
int n;vectorint level[N]; //每一层用一个vector来存数值,因为我们要层序遍历输出void build(int al,int ar,int bl,int br,int d) //d表示树的层数
{if(alar) return ; // 当alar时说明已经递归到最后一个子树int vala[ar]; //每个子树的根节点就是后续遍历的最后一个数字用val存下来level[d].push_back(val); //把每个根节点都存在 对应每一层的数组中去用于层序遍历输出int kp[val]; //k来表示根节点在中序遍历中的位置build(al,k-1-blal ,bl,k-1,d1); //递归左子树,下一层d1;build(k-blal,ar-1,k1,br,d1); //递归右子树
}int main()
{cinn;for(int i0;in;i) cina[i]; //a表示后序遍历for(int i0;in;i) cinb[i]; //b表示中序遍历;for(int i0;in;i) p[b[i]]i; //因为要确定中序遍历中左右子序的位置所以用p来存中序遍历中每个数字的位置build(0,n-1,0,n-1,0);for(int i0;in;i) //把每个level里面的数据输出出来for(int x:level[i])coutx ;return 0;
}补充 build的函数参数的表示如下图: 后序遍历中左子树的ar 的计算,列个方程即可,如下图:
2.递归求阶乘 请使用递归的方式求 n 的阶乘。 输入格式 共一行包含一个整数 n。 输出格式 共一行包含一个整数表示 n 的阶乘的值。 数据范围 1≤n≤10 输入样例 3输出样例 6代码实现 #includebits/stdc.h
using namespace std;int fac(int n)
{if(n1) return 1;else return fac(n-1)*n;
}int main()
{int n;cinn;int kfac(n);coutk;return 0;} 3.求斐波那契数列 请使用递归的方式求斐波那契数列的第 n 项下标从1开始。 斐波那契数列1,1,2,3,5…这个数列从第 3 项开始每一项都等于前两项之和 输入格式 共一行包含整数 n。 输出格式 共一行包含一个整数表示斐波那契数列的第 n 项。 数据范围 1≤n≤30 输入样例 4输出样例 3代码实现 #includebits/stdc.h
using namespace std;int fun(int n)
{if(n2) return 1;else return fun(n-1)fun(n-2);
}int main()
{int n;cinn;coutfun(n);return 0;
}虽然跟着y总学习但是简单题也要回顾
