Niuke:JZ36.二叉树与双向链表
文章目录
- Niuke:JZ36.二叉树与双向链表
- 题目描述
- 示例
- 思路分析
- 代码实现
Niuke:JZ36.二叉树与双向链表
题目描述
描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示

注意:
1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构
4.你不用输出双向链表,程序会根据你的返回值自动打印输出
输入描述:
二叉树的根节点
返回值描述:
双向链表的其中一个头节点。
示例
示例1
输入: {10,6,14,4,8,12,16} 复制 返回值: From left to right
are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4; 复制 说明:
输入题面图中二叉树,输出的时候将双向链表的头节点返回即可。
示例2
输入: {5,4,#,3,#,2,#,1} 复制 返回值: From left to right are:1,2,3,4,5;From
right to left are:5,4,3,2,1; 复制 说明:
5
/
4
/
3
/
2
/
1 树的形状如上图
思路分析
1: 通过中序遍历,让先递归的结点在后递归的前面,每次左递归之后将prev与当前结点root的左指针指向上一层函数栈帧递归的结点,让上一层函数栈帧树结点的右指针指向当前结点,故而在每一层递归时应该保存当前结点的
位置.
2: 当将二叉树连接成双向链表后,此时的pRootOfTree依旧指向树的根结点,此时应该将pRootOfTree指向双向链表表头.
注意:
1: 在对指针进行访问的时候一定要考虑指针不为空的情况.
2: 为了回溯时让上一层的prev依旧有效,此时的形参prev最好用引用.
3: 当第一层中序递归遍历结束,编译器会主动返回到上一层函数栈帧,也就是中序遍历该开始的地方.
代码实现
class Solution {
public:void InorderConvert( TreeNode* cur,TreeNode*& prev ){if( cur == nullptr )return;//如果不是空,就先往左子树遍历。InorderConvert(cur->left,prev);//走到这,第一个结点就为4.cur->left = prev;if( prev ){//执行这一步时prev不能指向空。prev->right = cur;}//更新prev;prev = cur; InorderConvert( cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev = nullptr;InorderConvert(pRootOfTree,prev);//题目要求返回链表的头。TreeNode* head = pRootOfTree;if( head){while( head->left ){head = head->left;}}return head;}
};相关文章:
Niuke:JZ36.二叉树与双向链表
文章目录Niuke:JZ36.二叉树与双向链表题目描述示例思路分析代码实现Niuke:JZ36.二叉树与双向链表 题目描述 描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示 注意: 1.要求不能创建任何新的结点,只…...
javaScript---读懂promise、async/await
一、Promise Promise 是一个 Es 6 提供的类,目的是更加优雅地书写复杂的异步任务。可以解决嵌套式的回调地域问题,Promise 将嵌套格式的代码变成了顺序格式的代码。 //回调地域 setTimeout(function () {console.log("红灯");setTimeout(function () {console.lo…...
【Linux】TCP编程流程
TCP编程流程 socket()创建套接字,套接字TCP协议选择流式服务SOCK_STREAM。 bind()指定套接字使用的IP地址和端口。IP地址是自己主机地址,端口为一个16位的整形值。 listen()方法创建监听队列。监听队列分为存放未完成三次握手的连接和完成三次握手的连…...
SuperMap iDesktop 下载安装,生成本地瓦片,以及发布本地瓦片服务
SuperMap iDesktop 是插件式桌面GIS软件,提供基础版、标准版、专业版和高级版四个版本,具备二三维一体化的数据处理、制图、分析、海图、二三维标绘等功能,支持对在线地图服务的无缝访问及云端资源的协同共享,可用于空间数据的生产…...
【ONE·Data || 常见排序说明】
总言 数据结构基础:排序相关内容。 文章目录总言1、基本介绍2、插入排序2.1、直接插入排序:InsertSort2.1.1、单趟2.1.2、总趟2.2、希尔排序(缩小增量排序):ShellSort2.2.1、预排序1.0:单组分别排序2.…...
本节作业之跟随鼠标的天使、模拟京东按键输入内容、模拟京东快递单号查询
本节作业之跟随鼠标的天使、模拟京东按键输入内容、模拟京东快递单号查询1 跟随鼠标的天使2 模拟京东按键输入内容3 模拟京东快递单号查询1 跟随鼠标的天使 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><met…...
ChatGPT 被大面积封号,到底发生什么了?
意大利数据保护机表示 OpenAI 公司不但非法收集大量意大利用户个人数据,没有设立检查 ChatGPT 用户年龄的机制。 ChatGPT 似乎正在遭遇一场滑铁卢。 3月31日, 大量用户在社交平台吐槽,自己花钱开通的 ChatGPT 账户已经无法登录,更…...
教你精通JavaSE语法之第十一章、认识异常
一、异常的概念与体系结构 1.1异常的概念 在Java中,将程序执行过程中发生的不正常行为称为异常。比如之前写代码时经常遇到的: 1.算术异常 System.out.println(10 / 0); // 执行结果 Exception in thread "main" java.lang.ArithmeticExcep…...
display、visibility、opacity隐藏元素的区别
display、visibility、opacity隐藏元素的区别 display: none 事件监听:无法进行DOM事件监听。 元素从网页中消失,并且不占据位置再次从网页中出现会引起重排 进而引起重绘继承:不会被子元素继承,因为子元素也不被渲染。 visib…...
Linux Shell 实现一键部署tomcat10+java13
tomcat 前言 Tomcat 服务器是一个免费的开放源代码的Web 应用服务器,属于轻量级应用服务器,在中小型系统和并发访问用户不是很多的场合下被普遍使用,是开发和调试JSP 程序的首选。对于一个初学者来说,可以这样认为,当…...
软硬皆施,WMS仓库管理系统+PDA,实现效率狂飙
人工经验Excel表格,是传统第三方仓储企业常用的管理模式。在这种管理模式下,对仓库员工的Excel操作能力、业务经验和工作素养要求极高。一旦员工的经验能力不足,就会导致仓库业务运行不顺畅,效率低下,而员工也会因长时…...
DJ3-2 传输层(第二节课)
目录 一、如何实现可靠数据传输 1. 需要解决地问题 2. 使用的描述方法 二、rdt1.0:完全可靠信道上的可靠数据传输 1. 前提条件 2. 有限状态机 FSM 三、rdt2.0:仅具有 bit 错误的信道上的可靠数据传输 1. 前提条件 2. 有限状态机 FSM 3. 停等协…...
FrIf-FrIf功能模块概述和与底层驱动的交互
总目录链接==>> AutoSAR入门和实战系列总目录 总目录链接==>> AutoSAR BSW高阶配置系列总目录 文章目录 1 FlexRay 接口模块概述2 与FlexRay底层驱动的交互1 FlexRay 接口模块概述 FlexRay 接口模块通过 FlexRay 驱动程序模块间接与 FlexRay 控制器通信。 它…...
【LeetCode】前 K 个高频元素(堆)
目录 1.题目要求: 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 2.解题思路: 代码展示: 1.题目要求: 给你一个整数数组 nums 和一个整数 k ࿰…...
Java ---多态
(一)定义 官方:多态是同一个行为具有多个不同表现形式或形态的能力。多态就是同一个接口,使用不同的实例而执行不同操作。 生活中的多态,如图所示: 多态性是对象多种表现形式的体现。 现实中,…...
13个程序员常用开发工具用途推荐整理
作为一名刚入门的程序员,选择合适的开发工具可以提高工作效率,加快学习进度。在本文中,我将向您推荐10个常用的开发工具,并通过简单的例子和代码来介绍它们的主要用途。 1. Visual Studio Code Visual Studio Code(V…...
TCP分包和粘包
文章目录TCP分包和粘包TCP分包TCP 粘包分包和粘包解决方案:TCP分包和粘包 TCP分包 场景:发送方发送字符串”helloworld”,接收方却分别接收到了两个数据包:字符串”hello”和”world”发送端发送了数量较多的数据,接…...
手撕深度学习中的优化器
深度学习中的优化算法采用的原理是梯度下降法,选取适当的初值params,不断迭代,进行目标函数的极小化,直到收敛。由于负梯度方向时使函数值下降最快的方向,在迭代的每一步,以负梯度方向更新params的值&#…...
英文打字小游戏
目录 1 实验目的 2 实验报告内容 3 实验题目 4 实验环境 5 实验分析和设计思路 6 流程分析和类图结构 编辑 7. 实验结果与测试分析 8. 总结 这周没有更新任何的文章,感到十分的抱歉。因为我们老师让我们做一个英文打字的小游戏,并要求撰写实验…...
PCB生产工艺流程三:生产PCB的内层线路有哪7步
PCB生产工艺流程三:生产PCB的内层线路有哪7步 在我们的PCB生产工艺流程的第一步就是内层线路,那么它的流程又有哪些步骤呢?接下来我们就以内层线路的流程为主题,进行详细的分析。 由半固化片和铜箔压合而成,用于…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
