当前位置: 首页 > 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;如果触发…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

拟合问题处理

在机器学习中&#xff0c;核心任务通常围绕模型训练和性能提升展开&#xff0c;但你提到的 “优化训练数据解决过拟合” 和 “提升泛化性能解决欠拟合” 需要结合更准确的概念进行梳理。以下是对机器学习核心任务的系统复习和修正&#xff1a; 一、机器学习的核心任务框架 机…...