【蓝桥集训】第六天——递归
作者:指针不指南吗
专栏: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]里面…
-
代码实现
#include<bits/stdc++.h> using namespace std;const int N=35; int a[N],b[N],p[N]; int n;vector<int> 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<n;i++) cin>>a[i]; //a表示后序遍历;for(int i=0;i<n;i++) cin>>b[i]; //b表示中序遍历;for(int i=0;i<n;i++) p[b[i]]=i; //因为要确定中序遍历中左右子序的位置,所以用p来存中序遍历中每个数字的位置;build(0,n-1,0,n-1,0);for(int i=0;i<n;i++) //把每个level里面的数据输出出来for(int x:level[i])cout<<x<<' ';return 0; }补充build的函数参数的表示如下图:
后序遍历中左子树的ar 的计算,列个方程即可,如下图:

2.递归求阶乘
请使用递归的方式求 n 的阶乘。
输入格式
共一行,包含一个整数 n。
输出格式
共一行,包含一个整数,表示 n 的阶乘的值。
数据范围
1≤n≤10
输入样例:
3输出样例:
6
-
代码实现
#include<bits/stdc++.h> using namespace std;int fac(int n) {if(n==1) return 1;else return fac(n-1)*n; }int main() {int n;cin>>n;int k=fac(n);cout<<k;return 0;}
3.求斐波那契数列
请使用递归的方式求斐波那契数列的第 n 项,下标从1开始。
斐波那契数列:1,1,2,3,5…这个数列从第 3 项开始,每一项都等于前两项之和
输入格式
共一行,包含整数 n。
输出格式
共一行,包含一个整数,表示斐波那契数列的第 n� 项。
数据范围
1≤n≤30
输入样例:
4输出样例:
3
-
代码实现
#include<bits/stdc++.h> using namespace std;int fun(int n) {if(n<=2) return 1;else return fun(n-1)+fun(n-2); }int main() {int n;cin>>n;cout<<fun(n);return 0; }
虽然跟着y总学习,但是简单题也要回顾

相关文章:
【蓝桥集训】第六天——递归
作者:指针不指南吗 专栏:Acwing 蓝桥集训每日一题 🐾或许会很慢,但是不可以停下来🐾 文章目录1.树的遍历2.递归求阶乘3.求斐波那契数列1.树的遍历 一个二叉树,树中每个节点的权值互不相同。 现在给出它的后…...
react源码中的hooks
今天,让我们一起深入探究 React Hook 的实现方法,以便更好的理解它。但是,它的各种神奇特性的不足是,一旦出现问题,调试非常困难,这是由于它的背后是由复杂的堆栈追踪(stack trace)支…...
038.Solidity入门——25调用其他合约的方法
Solidity 提供了几种方式用于调用其他合约:方法描述直接调用使用 address.call 函数,可以向另一个合约发送消息并返回结果。低级调用使用 address.call 或 address.callcode 函数,可以执行一个外部合约中的代码。与直接调用不同,低…...
Revit项目浏览器的标准设置应用和快速视图样板?
一、Revit项目浏览器的标准设置应用 设计院阶段的BIM应用,主要是Revit出施工图方面,需要涉及到很多标准的制定方面的问题,而且这个标准不仅仅是一个命名标准,还有很多的符合本院的出图标准等等,本期就不做详细讨论&…...
安装MQTT Server遇到报错“cannot verify mosquitto.org‘s certificate”,该如何解决?
MQTT是基于发布/订阅的轻量级即时通讯协议,很适合用于低带宽、不稳定的网络中进行远程传感器和控制设备通讯等操作中。在我们的软件研发中,也经常使用MQTT协议进行消息通信等。今天来和大家分享一些关于在安装MQTT Server中遇到的疑难问题及解决思路。当…...
程序员如何向架构师转型?看完就明白该怎么做了
软件行业技术开发从业人员众多,但具备若干年开发经验的普通的开发人员往往面临个人发展的瓶颈,即如何从普通开发人员转型成高层次的系统架构师和技术管理人员。想成为一名架构师,应当具备全面的知识体系,需要进行系统的学习和实践…...
Flask入门(9):蓝图
目录9.蓝图9.1 概述9.2 蓝图项目结构结构1结构29.3 添加前缀9.4 静态文件9.5 模板9.6 构建 URLs9.蓝图 参考:http://www.pythondoc.com/flask/blueprints.html 9.1 概述 Flask 使用了 蓝图 的概念在一个应用或者跨应用中构建应用组件以及支持通用模式。 蓝图很好…...
跑步戴哪种耳机好,最适合运动跑步的蓝牙耳机
经常跑步使用的耳机,还是要选择佩戴着舒适以及牢固的运动耳机最为合适,在运动当中会遇到耳机掉落或者长时间佩戴耳道感到难受的现象发生,那么什么蓝牙耳机是最适合运动当中佩戴呢?下面这些耳机分享希望能够帮助大家。 1、南卡Run…...
微信小程序实现瀑布流布局
微信小程序实现瀑布流布局1、简单实例,纯图片后台返回图片高度https://blog.csdn.net/qq_45967222/article/details/1190318762、纯图片后台返回图片高度、通过wx.getImageInfo获取在线图片高度、按照奇数偶数来显示https://blog.csdn.net/baidu_35290582/article/d…...
2023最新网络工程师HCIA-Datacom“1000”道题库,光速刷题拿证
HCIA认证是华为认证体系的初级认证,可以说是网工进入IT行业的一张从业资格证! HCIA-Datacom考试覆盖数通基础知识 包括 TCP/IP 协议栈基础知识,OSPF 路由协议基本原理以及在华为路由器中的配置实现,以太网技术、生成树、VLAN 原…...
[蓝桥杯] 递归与递推习题训练
文章目录 一、递归实现指数型枚举 1、1 题目描述 1、2 题解关键思路与解答 二、递归实现排列型枚举 2、1 题目描述 2、2 题解关键思路与解答 三、递归实现组合型枚举 3、1 题目描述 3、2 题解关键思路与解答 四、带分数 4、1 题目描述 4、2 题解关键思路与解答 五、费解的开关…...
领航智能汽车信息安全新征程 | 云驰未来乔迁新址
2月20日,在北京朝阳百子湾东朝时代创意园,云驰未来迎来乔迁之喜,智能汽车和自动驾驶领域的行业领导、合作伙伴与客户、投资人及媒体嘉宾齐聚现场,共同见证云驰未来迈上新的发展征程。 作为中国智能网联汽车和自动驾驶信息安全行业…...
Kaldi语音识别技术(七) ----- 训练GMM
Kaldi语音识别技术(七) ----- GMM 文章目录Kaldi语音识别技术(七) ----- GMM训练GMMtrain_mono.sh 用于训练GMM训练GMM—生成文件训练GMM—final模型查看训练GMM—final.occs查看训练GMM—对齐信息查看训练GMM—fsts.*.gz查看训练GMM—tree决策树查看align_si.sh 用于对齐训练G…...
Java 集合基础
文章目录一、集合概念二、ArrayList1. 构造方法和添加方法2. 常用方法三、案例演示1. 存储字符串并遍历2. 存储学生对象并遍历3. 键盘录入学生对象并遍历一、集合概念 编程的时候如果要存储多个数据,使用长度固定的数组存储格式,不一定满足我们的需要&a…...
Day896.MySql的kill命令 -MySQL实战
MySql的kill命令 Hi,我是阿昌,今天学习记录的是关于MySql的kill命令的内容。 在 MySQL 中有两个 kill 命令: 一个是 kill query 线程 id,表示终止这个线程中正在执行的语句;一个是 kill connection 线程 id&#…...
L2-010 排座位
布置宴席最微妙的事情,就是给前来参宴的各位宾客安排座位。无论如何,总不能把两个死对头排到同一张宴会桌旁!这个艰巨任务现在就交给你,对任何一对客人,请编写程序告诉主人他们是否能被安排同席。 输入格式࿱…...
C++的完美讲解,还不快来看看?
目录 简介: 创建C程序: Windows编译简介: Hello,C World! 简介: C融合了3中不同的编程传统:C语言代表的过程性传统、C在C语言基础上添加的类代表的面向对象语言的传统以及C模板支持的通用编程传统。一般来说,计算机语言…...
C语言学习_DAY_5_循环结构while和for语句【C语言学习笔记】
高质量博主,点个关注不迷路🌸🌸🌸! 目录 I. 案例引入 II. while语句 III. do while语句 IV. for语句 前言: 书接上回,判断结构已经解决,接下来是另一种很重要的结构:循环结构的实…...
JavaScript高级程序设计读书分享之4章——4.3垃圾回收
JavaScript高级程序设计(第4版)读书分享笔记记录 适用于刚入门前端的同志 4.3.3 性能 垃圾回收程序会周期性运行,如果内存中分配了很多变量,则可能造成性能损失,因此垃圾回收的 时间调度很重要。尤其是在内存有限的移动设备上,垃圾…...
Java线程的6 种状态
Java 线程的状态 Java线程有六种状态: 初始(NEW)、运行(RUNNABLE)、阻塞(BLOCKED)、 等待(WAITING)、超时等待(TIMED_WAITING)、终止(…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
