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生产工艺流程的第一步就是内层线路,那么它的流程又有哪些步骤呢?接下来我们就以内层线路的流程为主题,进行详细的分析。 由半固化片和铜箔压合而成,用于…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
