Leetcode-每日一题【剑指 Offer 36. 二叉搜索树与双向链表】
题目
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解题思路
1.题目要求将二叉搜索树转换成一个排序的循环双向链表,既然他需要排序,那么我们就对二叉搜索树进行中序遍历,这样我们就可以得到有顺序的序列。
2.我们新建一个队列 queue ,然后对二叉搜索树进行中序遍历,并且将遍历的结果入队。
3.遍历结束后我们就得到了一个有序队列,这时我们只需要使用 whie 循环让队列中的元素出队并且将元素做一下连接,让前一个元素的right指针指向后一个元素,让后一个元素的left指针指向前一个元素。最后不要忘记首位元素的连接。
代码实现
class Solution {public Node treeToDoublyList(Node root) {if(root == null){return null;}Queue<Node> queue = new LinkedList<>();inOrder(root, queue);Node head = queue.poll();Node pre = head;while(!queue.isEmpty()){Node cur = queue.poll();pre.right = cur;cur.left = pre;pre = cur;}pre.right = head;head.left = pre;return head;}void inOrder(Node root, Queue<Node> queue){if(root == null){return;}inOrder(root.left, queue);queue.add(root);inOrder(root.right, queue);}
}
测试结果

相关文章:
Leetcode-每日一题【剑指 Offer 36. 二叉搜索树与双向链表】
题目 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为双向循环链表…...
ctfshow-萌新专属红包题
0x00 前言 CTF 加解密合集CTF Web合集 0x01 题目 0x02 Write Up 访问之后是一个登录页面,扫了目录,试了sql注入,没办法于是跑一跑弱口令,所以有事没事,admin弱口令跑一跑 搜索 微信公众号 皓月当空w 发送关键字 字典…...
谷歌面试-扔鸡蛋
今天想跟大家分享一个有意思的面试题,这让我再一次感叹思维的奇妙,接下来我们一起看看吧~ 首先来看看题目: 你有2颗鸡蛋,需要以最少的尝试次数来判断在100层的高楼上,哪一层楼是鸡蛋的安全层。 换句话说,…...
Unity血条制作
一、使用UGUI制作血条 我一般使用image制作血条,当然,也可以使用滑动组件Slider。image的具体操作步骤如下 普通血条 1、在Hierarchy面板中,创建两个image组件,将其中一个设置为另外一个的子节点 2、在Inspector面板中&#…...
vue,uniapp生成二维码
话不多说直接开干 先是vue的 1,首先按照一下依赖 npm install --save qrcode 2,在需要使用的页面引入 import QRCode from qrcode; 3,使用 const codeDetail (item) > {//这个item.code是要生成的数据,我的是一串数字QRCode.toDataURL(item.co…...
分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测
分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测 目录 分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测…...
STM32启动模式详解
文章目录 前置知识1. 单片机最小系统组成2. BOOT电路3. 三种启动模式4. 存储器映射 从主FLASH启动从系统存储区启动从SRAM启动 前置知识 1. 单片机最小系统组成 一个单片机最小系统由电源、晶振、下载电路、BOOT电路、和复位电路组成。少一个单片机都启动不了。 2. BOOT电路 …...
go语言中的切片
切片底层 切片(Slice)是一个拥有相同类型元素的可变长度的序列。它是基于数组类型做的一层封装。它非常灵活,支持自动扩容。 切片是一个引用类型,它的内部结构包含地址、长度和容量。切片一般用于快速地操作一块数据集合。 切片…...
HTML-常见标签、HTML5新特性
HTML 软件架构 1.C/S架构 (1) C/S架构即Client/Server(客户机/服务器)结构。 (2) C/S 架构特点 C/S结构在技术上很成熟,它的主要特点是交互性强、具有安全的存取模式、网络通信量低、响应速度快、利于处理大量数据。但是该结构的程序是…...
微信有自己的“知乎”,微信问一问来了!
这几个月来,微信问一问一直挺火的,有人涨粉,有人变现,有人引流~ 这个全新的流量入口对流量玩家来说又是一波巨大的流量红利。 微信问一问就类似于微信版的知乎,未来将对知乎产生一定竞争压力。 依托于微信这个庞大的流…...
[MyBatis系列③]动态SQL
目录 1、简介 2、if标签 3、foreach标签 4、SQL抽取 ⭐MyBatis系列①:增删改查 ⭐MyBatis系列②:两种Dao开发方式 1、简介 开发中在MyBatis映射文件配置SQL语句,但是前面配置的都是比较简单的,不涉及稍复杂的业务场景。想要应…...
开始MySQL之路—— DDL语法、DML语法、DQL语法基本操作详解
DDL语法 DDL(Data Definition Language) 数据定义语言,该语言部分包括以下内容。 对数据库的常用操作 对表结构的常用操作 修改表结构 对数据库的常用操作 1: 查看当前所有的数据库 show databases; 2:创建数据库 create dat…...
Java“牵手”天猫整店商品API接口数据,通过店铺ID获取整店商品详情数据,天猫店铺所有商品API申请指南
天猫平台店铺所有商品数据接口是开放平台提供的一种API接口,通过调用API接口,开发者可以获取天猫整店的商品的标题、价格、库存、月销量、总销量、库存、详情描述、图片、价格信息等详细信息 。 获取店铺所有商品接口API是一种用于获取电商平台上商品详…...
用AI重构的钉钉,“钱”路在何方?
点击关注 文|郝 鑫,编|刘雨琦 钉钉2023年生态大会,离开了两年的无招,遇到了单飞9天的钉钉。 “做小钉钉、做好钉钉、做酷钉钉”,无招重申了钉钉的方向。 无招提到的三点,再加上“高质量增长”…...
批量根据excel数据绘制柱状图
要批量根据Excel数据绘制柱状图,可以使用Python中的pandas和matplotlib库来实现。下面是示例代码: import pandas as pd import matplotlib.pyplot as plt import os def draw_bar_chart_from_excel(file_path, x_column, y_column, output_folder): …...
浅谈 Java 中的 Lambda 表达式
更好的阅读体验 \huge{\color{red}{更好的阅读体验}} 更好的阅读体验 Lambda 表达式是一种匿名函数,它可以作为参数传递给方法或存储在变量中。在 Java8 中,它和函数式接口一起,共同构建了函数式编程的框架。 什么是函数式编程 函数式编程是…...
闭包的概念
概念 内层函数可以访问到外层函数的变量和参数,即一个函数和它周围状态捆绑在一起的组合。 举例 函数作为返回值 // 函数作为返回值 function test(){const a 1;return function() {console.log(a:,a);} }const fn test(); const a 6; fn(); // 1 2. 函数作…...
openGauss学习笔记-52 openGauss 高级特性-LLVM
文章目录 openGauss学习笔记-52 openGauss 高级特性-LLVM52.1 适用场景52.2 非适用场景52.3 其他因素对LLVM性能的影响52.4 LLVM使用建议 openGauss学习笔记-52 openGauss 高级特性-LLVM openGauss借助LLVM(Low Level Virtual Machine)提供的库函数&…...
MySQL 8.0字符集校正
MySQL升级为8.0版本时,之前版本的字符集往往是不同的,需要校正。 执行下面的三个SQL语句的查询结果,可以从库、表、列三个层面对字符集进行校正。 库 select concat(alter database , schema_name, default character set utf8mb4 collate …...
软考:中级软件设计师:数据库恢复与备份,故障与恢复,反规范化
软考:中级软件设计师:数据库恢复与备份 提示:系列被面试官问的问题,我自己当时不会,所以下来自己复盘一下,认真学习和总结,以应对未来更多的可能性 关于互联网大厂的笔试面试,都是需要细心准备…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
