当前位置: 首页 > news >正文

【C++】二叉树之力扣经典题目1——详解二叉树的递归遍历,二叉树的层次遍历

如有错误,欢迎指正。
如有不理解的地方,可以私信问我。

文章目录

  • 题目1:根据二叉树创建字符串
    • 题目
    • 实例
    • 思路与解析
    • 代码实现
  • 题目2:二叉树的层序遍历
    • 题目
    • 思路与解析
    • 代码实现


题目1:根据二叉树创建字符串

点击进入题目链接——>力扣–根据二叉树创建字符串

题目

在这里插入图片描述

实例

在这里插入图片描述

思路与解析

题目的要求:二叉树已给出,我们需要采用前序遍历的方式,遍历二叉树,空节点用()表示
即用()标识左右子树,但是结果需要省略不必要的空括号对,并把遍历的结果放在字符串中,最后返回的是字符串。

思路解析:这道题是二叉树层序遍历的变形,前序遍历—根,左子树,右子树—采用递归,我们主要解决的是空括号对的省略问题,明确什么时候需要省略。

步骤

  • 如果是空树就直接返回空字符串
  • 创建存放前序遍历结果的字符串要将整数转换成字符串,才能插入到字符串对象中
  • 我们可以使用递归的方法得到二叉树的前序遍历,并在递归时加上额外的括号。用()标识左右子树,但是需要省略所有不必要的空括号对
  • 如果当前节点有两个孩子,那我们在递归时,需要在两个孩子的结果外都加上一层括号;
  • 如果当前节点没有孩子,那我们不需要在节点后面加上任何括号;
  • 如果当前节点只有左孩子,那我们在递归时,只需要在左孩子的结果外加上一层括号,而不需要给右孩子加上任何括号;
  • 如果当前节点只有右孩子,没有左孩子,那我们在递归时,需要先加上一层空的括号 ‘()’,‘()’ 表示左孩子为空,再对右孩子进行递归,并在结果外加上一层括号。
  • 最后返回存放层序遍历结果的字符串

代码实现

 //思路:前序遍历---根,左子树,右子树---采用递归
class Solution {
public:string tree2str(TreeNode* root) {//1.如果是空树就返回空字符串if(root==nullptr){return string();}string str;//存放前序遍历结果的字符串//【根】str+=to_string(root->val);//要将整数转换成字符串//用()标识左右子树,但是需要省略所有不必要的开括号对//【左子树】//2.左子树不为空,所以我们需要标示左子树if(root->left){str+="(";//字符串+=用""或者‘’都可以str+=tree2str(root->left);str+=')';}else if(root->right)//3.如果左子树为空,右子树不为空,根据示例2,左子树为空,()不能省略,我们就手动加上{str+="()";}//【右子树】//4.对右子树的处理,我们需要标识右子树,从示例1中得,右子树为空,不需要加上()if(root->right){str+='(';str+=tree2str(root->right);str+=')';}return str;}
};

题目2:二叉树的层序遍历

点击进入题目链接——>力扣—二叉树的层序遍历

题目

在这里插入图片描述

思路与解析

思路:这道题考查二叉树的层序遍历,是层序遍历的变形,与普通的层序遍历不同的是,这道题的函数要求我们返回一个二维数组,所以我们需要先创建一个二维数组,二维数组中的一维数组分别存放二叉树每层的数据,根据题目的实例,我们要一层一层的遍历,将每层的遍历分别放在一维数组中,并利用队列的帮助进行层序遍历。接下来我们利用一个变量levelSize,这样可以准确的分开每层的数据,分别放在一维数组中。

代码实现

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;//构建二维数组queue<TreeNode*> q;//存放二叉树结点的队列int levelSize=0;//每层的的结点个数if(root){q.push(root);levelSize=1;}while(!empty(q)){//构建一维数组,分别存放每层遍历的结果,一次循环结束后就push进二维数组vector<int> v;//levelSiz记录当前层的数据个数while(levelSize--)//关键思路:保证层序遍历{TreeNode* front=q.front();//保留队头结点地址q.pop();//出队头结点v.push_back(front->val);//将每层拿到的数据放进一维数组//push左子树if(front->left){q.push(front->left);}//push右子树if(front->right){q.push(front->right);}}levelSize=q.size();//将levelSize更改成当前成的数据个数vv.push_back(v);//将一维数组v(分别存放这每层的数据)push进二维数组vv中}return vv;}
};

变化:给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)点击进入题目:二叉树层序遍历II

解决方法:得到从上自下的层序遍历的二维数组后,用reverse函数,将二维数组中的内容翻转一下即可。

相关文章:

【C++】二叉树之力扣经典题目1——详解二叉树的递归遍历,二叉树的层次遍历

如有错误&#xff0c;欢迎指正。 如有不理解的地方&#xff0c;可以私信问我。 文章目录题目1&#xff1a;根据二叉树创建字符串题目实例思路与解析代码实现题目2&#xff1a;二叉树的层序遍历题目思路与解析代码实现题目1&#xff1a;根据二叉树创建字符串 点击进入题目链接—…...

MySQL数据库调优————SQL性能分析

TIPS 本文基于MySQL 8.0 本文探讨如何深入SQL内部&#xff0c;去分析其性能&#xff0c;包括了三种方式&#xff1a; SHOW PROFILEINFORMATION_SCHEMA.PROFILINGPERFORMANCE_SCHEMA SHOW PROFILE SHOW PROFILE是MySQL的一个性能分析命令&#xff0c;可以跟踪SQL各种资源消耗。…...

sql数据库高级编程总结(一)

1、数学函数&#xff1a;操作一个数据&#xff0c;返回一个结果 &#xff08;1&#xff09;取上限 ceiling 如果有一个小数就取大于它的一个最小整数 列如9.5 就会取到 10 select code,name,ceiling(price) from car &#xff08;2&#xff09;取下限 floor 如果有一个小数就…...

软件工程(5)--喷泉模型

前言 这是基于我所学习的软件工程课程总结的第五篇文章。 迭代是软件开发过程中普遍存在的一种内在属性。经验表明&#xff0c;软件过程各个阶段之间的迭代或一个阶段内各个工作步骤之间的迭代&#xff0c;在面向对象范型中比在结构化范型中更常见。 一般说来&#xff0c;使用…...

SM2数字签名

文章目录6. 签名流程7. 验签流程实现参考资料6. 签名流程 M’ ZA || Msge Hash(M’)&#xff0c;并转为大数&#xff1b;生成随机数k&#xff0c;范围0<k<n&#xff1b;计算kG (x1, y1)r (e x1) mod n, 若r0或(rkn)则重新生成k&#xff1b;s (k-rd) / (1d) mod n&…...

RPA+保险后台部门擦出不一样“火花” | RPA案例

在保险行业中&#xff0c;后台业务线主要是为前台和中台等提供支持&#xff0c;提供公司整体运营服务&#xff0c;包括财务、信息、人力、综合办等。相对于中前台部门&#xff0c;后台部门离核心价值链更远一些&#xff0c;更偏支持部门&#xff0c;其中某些岗位与业务相关度强…...

设备树相关概念的理解

设备树 定义 设备树是描述硬件信息的一种树形结构&#xff0c;设备树文件会在内核启动后被内核解析得到对应设备的具体信息。 树形结构就自然会存在节点&#xff0c;硬件设备信息就存储再设备树中的节点上&#xff0c;即设备节点。而一个设备节点中可以存储硬件的多个不同属性…...

ubuntu20.04下配置深度学习环境GPU

卸载子系统 C:\Users\thzn>wsl --list 适用于 Linux 的 Windows 子系统分发版: docker-desktop (默认) docker-desktop-data Ubuntu-18.04 Ubuntu-22.04 Ubuntu-20.04 C:\Users\thzn>wsl --unregister Ubuntu-18.04 ubuntu 换源 https://www.cnblogs.com/Horizon-asd/p…...

用egg.js来写一个api管理系统(一)

Egg.js是一个基于Node.js的企业级开发框架&#xff0c;非常适合构建API服务。 安装egg.js 首先&#xff0c;您需要安装Node.js和npm&#xff08;Node Package Manager&#xff09;。然后&#xff0c;您可以通过运行以下命令来安装Egg.js&#xff1a; npm i egg --save然后&a…...

企业数字化转型和升级:架构设计方法与实践

目录 企业架构整体结构 企业架构的驱动力 企业架构的基本概念 企业架构的发展 企业架构框架理论 主流企业架构框架之对比 企业架构整体结构 图例&#xff1a;企业架构整体结构 企业架构整体结构从战略层、规划层、落地层这三层来分别对应企业架构中 业务、架构和实施的各种重要…...

【LeetCode】环形链表 II [M](链表)

142. 环形链表 II - 力扣&#xff08;LeetCode&#xff09; 一、题目 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链…...

Unity之如何实现一个VR任务(剧情)系统

一.前言 最近再做一个VR项目,里面有大量的剧情和VR操作任务。 比如: 1.张三说了什么话,干了什么事,然后,李四又说了什么,做了什么动画,完了之后,场景中某个物体高亮,让我们触摸或者射线点击(pc的话鼠标点击)和其发生交互。 2.我们使用VR手柄或者鼠标与场景中的一个…...

k8s核心概念与kubectl命令行工具的使用

k8s官方文档Kubernetes 文档 | Kubernetes作用&#xff1a;kubernetes用于容器化应用程序的部署&#xff0c;扩展和管理。目标&#xff1a;是让部署容器化应用简单高效。Kubernetes集群架构与组件 Master组件 kube-apiserverkubernetes API&#xff0c;集群的统一入口&#xff…...

【零基础入门前端系列】—无序列表、有序列表、定义列表(四)

一、HTML无序列表 无序列表是一个项目的列表&#xff0c;此列项目使用粗体圆点&#xff08;典型的小黑圆圈&#xff09;进行标记。 无序列表使用 <ul> 标签 <ul> <li>Coffee</li> <li>Milk</li> </ul>嵌套结构&#xff1a; <…...

为什么重写equals还要重写hashcode方法

目录equals方法hashCode方法为什么要一起重写&#xff1f;总结面试如何回答重写 equals 时为什么一定要重写 hashCode&#xff1f;要想了解这个问题的根本原因&#xff0c;我们还得先从这两个方法开始说起。 以下是关于hashcode的一些规定&#xff1a; 两个对象相等&#xff0…...

电子技术——电流镜负载的差分放大器

电子技术——电流镜负载的差分放大器 目前我们学习的差分放大器都是使用的是差分输出的方式&#xff0c;即在两个漏极之间获取电压。差分输出主要有以下优势&#xff1a; 降低了共模信号的增益&#xff0c;提高了共模抑制比。降低了输入偏移电压。提升了差分输入的增益。 由于…...

go面试题

1.json包在使用的时候&#xff0c;结构体里的变量不加tag能不能正常转成json里的字段&#xff1f; 如果变量首字母小写&#xff0c;则为private。无论如何不能转&#xff0c;因为取不到反射信息。如果变量首字母大写&#xff0c;则为public。 不加tag&#xff0c;可以正常转为j…...

攻防世界-Confusion1

题目 访问题目场景 某天&#xff0c;Bob说&#xff1a;PHP是最好的语言&#xff0c;但是Alice不赞同。所以Alice编写了这个网站证明。在她还没有写完的时候&#xff0c;我发现其存在问题。(请不要使用扫描器) 然后结合图片我们知道&#xff0c;这个网址是python写的&#xff0…...

机器学习实战--梯度下降法进行波士顿房价预测

前言&#xff1a; Hello大家好&#xff0c;我是Dream。 今天来学习一下如何使用机器学习梯度下降法进行波士顿房价预测&#xff0c;这是简单的一个demo&#xff0c;主要展示的是一些小小的思路~ 本文目录&#xff1a;一、波士顿房价预测1.全部的数据可视化2.地理数据可视化3.房…...

黑马】后台管理-项目优化和上线

一。项目优化优化1&#xff0c;加载进度条显示安装一个运行依赖&#xff0c;nprogress然后导包&#xff0c;调用对象展示和隐藏在main中基于拦截器实现展示进度条和隐藏进度条的效果如果触发请求拦截器&#xff0c;证明发起请求&#xff0c;希望展示进度条&#xff0c;如果触发…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...