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

从lc114. 二叉树展开为链表到lc-LCR 155二叉搜索树转化为排序的双向链表

1 lc114. 二叉树展开为链表

1.1 描述

进阶:你可以使用原地算法(O(1) 额外空间)展开这棵树吗?
在这里插入图片描述

1.2 解法一:

先序遍历这棵树并且将节点加入到一个list中,随后按顺序将list中的每一个元素的left指针置换为空,right指针指向下一个节点

1.3 解法二:

按照先序遍历的倒叙方式遍历这棵二叉树,然后同时操作这个节点的左右指针。

class Solution {TreeNode pre;public void flatten(TreeNode root) {if(root==null){return;}flatten(root.right);flatten(root.left);root.right=pre;root.left=null;pre=root;}
}

1.3.1 为什么不能采用先序遍历,然后在过程中将左右指针进行相应的链接和置空呢?

答:因为先根遍历时进行正向的链接,会导致右子树断开,后续就无法遍历右子树中的节点

1.3.2 为什么先序的倒叙是代码中这样写的呢

答:先序遍历是"根-左-右",那么先序的倒叙应该是"右-左-根"

1.3.3 为什么先序的倒叙可以避免右子树的撕裂?

答:其实右子树无论如何都会被断开一次,但是因为右子树中的节点都已经被正确处理完后才开始重新接上,后续就不需要遍历右子树了。

1.3.4 如果让展开后的单链表应该同样使用 TreeNode ,其中 left 子指针指向链表中下一个结点,而right 子指针始终为 null ,解法是不是基本相同?

答:对,遍历结构还是先序的倒叙遍历

class Solution {TreeNode pre;public void flatten(TreeNode root) {if(root==null){return;}flatten(root.right);flatten(root.left);root.left=pre;root.right=null;pre=root;}
}

2 LCR 155二叉搜索树转化为排序的双向链表

多种方法解决leetcode经典题目-LCR 155. 将二叉搜索树转化为排序的双向链表, 同时弄透引用变更带来的bug

相关文章:

从lc114. 二叉树展开为链表到lc-LCR 155二叉搜索树转化为排序的双向链表

1 lc114. 二叉树展开为链表 1.1 描述 进阶:你可以使用原地算法(O(1) 额外空间)展开这棵树吗? 1.2 解法一: 先序遍历这棵树并且将节点加入到一个list中,随后按顺序将list中的每一个元素的left指针置换为…...

做读书笔记时的一个高效小技巧

你好,我是 EarlGrey,一名双语学习者,会一点编程,目前已翻译出版《Python 无师自通》、《Python 并行编程手册》等书籍。 在这里,我会持续和大家分享好书、好工具和高效生活、工作技巧,欢迎大家一起提升认知…...

Redis7.x 高级篇

Redis7.x 高级篇 Redis版本发行时间Redis单线程说的是什么东西 Redis版本发行时间 Redis单线程说的是什么东西...

2023辽宁省数学建模B题数据驱动的水下导航适配区分类预测完整原创论文分享(python求解)

大家好呀,从发布赛题一直到现在,总算完成了辽宁省数学建模B题完整的成品论文。 本论文可以保证原创,保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品论文。 B用Python+SPSSPRO求解&…...

向量数据库的崛起与多元化场景创新

向量数据库的崛起与多元化场景创新 前言: 在当今数字化时代,数据被认为是黄金,对于企业、科学家和决策者而言都具有巨大的价值。然而,随着数据规模的不断增长,有效地管理、存储和检索数据变得愈发复杂。这就引入了向量…...

面试10000次依然会问的【ReentrantLock】,你还不会?

引言 在并发编程的世界中,ReentrantLock扮演着至关重要的角色。它是一个实现了重入特性的互斥锁,提供了比synchronized关键字更加灵活的锁定机制。ReentrantLock属于java.util.concurrent.locks包,是Java并发API的一部分。 与传统的synchro…...

Bat批量处理

一:创建文件夹 excel创建文件 复制出来新建文本文件 另存为bat 双击bat 二:批量移动文件 A列:获取的文件名列表 dir /b/o:n> original.txt B列:填充序号 C列公式:每隔9行增加1 INT((ROW(B1)-1)/9)1 D列公式&am…...

【一、http】go的http基本请求方法

1、http的基本请求 package mainimport ("bytes""fmt""io""net/http""net/url" )func post(){r, err : http.Post("http://httpbin.org/post", "", nil)if err ! nil {fmt.Println("ss")}de…...

【软考中级】软件设计师-下午题

下午题 试题一 黑洞:加工有输入无输出 白洞(奇迹):加工有输出无输入 灰洞:数据流输入的加工不足以产生输出 结构化语言: IF *** THEN ELSE IF *** THEN ******* END IF END IF 数据流的父子图平衡,如果父子图平衡就不…...

(03)Mycat实现读写分离

1、schema.xml <?xml version"1.0"?> <!DOCTYPE mycat:schema SYSTEM "schema.dtd"> <mycat:schema xmlns:mycat"http://io.mycat/"><schema name"TESTDB" checkSQLschema"false" sqlMaxLimit"…...

[SSD综述1.7] SSD接口形态: SATA、M.2、U.2、PCIe、BGA

依公知及经验整理,原创保护,禁止转载。 专栏 《SSD入门到精通系列》 <<<< 返回总目录 <<<< 前言 犹记得当年Windows 7系统体验指数中,那5.9分磁盘分数,在其余四项的7.9分面前,似乎已经告诉我们机械硬盘注定被时代淘汰。势如破竹的SSD固态硬盘,彻…...

20.5 OpenSSL 套接字RSA加密传输

RSA算法同样可以用于加密传输&#xff0c;但此类加密算法虽然非常安全&#xff0c;但通常不会用于大量的数据传输&#xff0c;这是因为RSA算法加解密过程涉及大量的数学运算&#xff0c;尤其是模幂运算&#xff08;即计算大数的幂模运算&#xff09;&#xff0c;这些运算对于计…...

C#中的19个LINQ to XML 类

System.Xml.Linq 命名空间包含 LINQ to XML 的19个类。 LINQ to XML 是内存中的 XML 编程接口&#xff0c;使能轻松有效地修改 XML 文档。 微软在 LINQ 上投入了很大的精力&#xff0c;使我们在编程时感觉到很舒服。处理 XML 时使用最多的三个类&#xff1a;XElement、XAttribu…...

取消elementUI中table的选中状态和勾选状态赋值

一、取消所有选中 1、表格上绑定ref 2、清空用户选中数据 this.$refs.loopRef.clearSelection()二、勾选状态赋值 获取数据&#xff0c;flag为true则是选中状态&#xff0c;并将前面勾选框设为选中状态 this.listData.forEach(item> {if(row.flag1){this.$refs.loopRef.to…...

LeetCode 72. 编辑距离(动态规划)

题目&#xff1a; 链接&#xff1a;LeetCode 72. 编辑距离 难度&#xff1a;中等 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 示例…...

Bytedance揭秘OpenAI大模型: GPT-3到GPT-4进化路径

文章目录 探秘GPT-3到GPT-4进化之路1、SFT&#xff1a;早期GPT进化的推动者2、RLHF和SFT&#xff1a;编码能力提升的功臣3、代码加入预训练&#xff0c;对推理帮助最大4、“跷跷板”现象 论文地址项目链接Reference GPT-Fathom: Benchmarking Large Language Models to Deciphe…...

第二十六章 BEV感知系列三(车道线感知)

前言 近期参与到了手写AI的车道线检测的学习中去&#xff0c;以此系列笔记记录学习与思考的全过程。车道线检测系列会持续更新&#xff0c;力求完整精炼&#xff0c;引人启示。所需前期知识&#xff0c;可以结合手写AI进行系统的学习。 BEV感知系列是对论文Delving into the De…...

总结几个面试题

目录 1. this 指针存在哪里 2. this指针可以为空吗&#xff1f; 3. 结构体怎么对齐&#xff1f;为什么要进行内存对齐&#xff1f; 4. 如何让结构体按照指定的对齐方式对齐&#xff1f;能否按照3、4、5即任意字节对齐&#xff1f; 5. 什么是大小端&#xff1f;如何测…...

【多线程】并发问题

public class BuyTicket implements Runnable{private int ticketNums10;Overridepublic void run() {for(int i1;i<ticketNums;i){if(ticketNums<0){break;}System.out.println(Thread.currentThread().getName() "抢到了第" i "张票");ticketNu…...

httpclient工具类(支持泛型转换)

1、网上搜到的httpclient工具类的问题&#xff1a; 1.1、如下图我们都能够发现这种封装的问题&#xff1a; 代码繁杂、充斥了很多重复性代码返回值单一&#xff0c;无法拿到对应的Java Bean对象及List对象集合实际场景中会对接大量第三方的OPEN API&#xff0c;下述方法的扩展…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...