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

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

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
注意:此题对比原题有改动。
💡思路:中序递归遍历
由二叉搜索树的性质:中序遍历即为 递增序列。所以可以在中序遍历的时候完成双向链表的转化:
定义两个结点 head 和 end 分别指向已转换链表的 头结点 和 尾结点;
inOrder(root) :中序递归遍历:
- 终止条件:当
root为空时,返回; - 递归调用左子树:
inOrder(root.left); - 构建链表:
- 当到达树的最左边的第一个叶子节点,即为
head; - 当
end不为空时,修改双向结点引用, 即end.right = root,root.left = end; - 更新
end,即end = root;
- 当到达树的最左边的第一个叶子节点,即为
- 递归调用右子树,
inOrder(root.right)。
最后将双向链表首尾相连:head.left = end , end.right = head。
🍁代码:(C++、Java)
C++
/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val = _val;left = NULL;right = NULL;}Node(int _val, Node* _left, Node* _right) {val = _val;left = _left;right = _right;}
};
*/
class Solution {
private:Node* head = nullptr;Node* end = nullptr;void inOrder(Node* root){if(root == nullptr) return;inOrder(root->left);if(head == nullptr) head = root;//树的最左边的第一个叶子节点为headroot->left = end;if(end != nullptr) end->right = root;end = root;inOrder(root->right);}
public:Node* treeToDoublyList(Node* root) {inOrder(root);if(head != nullptr){head->left = end;end->right = head;}return head;}
};
Java
/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node() {}public Node(int _val) {val = _val;}public Node(int _val,Node _left,Node _right) {val = _val;left = _left;right = _right;}
};
*/
class Solution {private Node head = null;private Node end = null;private void inOrder(Node root){if(root == null) return;inOrder(root.left);if(head == null) head = root;//树的最左边的第一个叶子节点为headroot.left = end;if(end != null) end.right = root;end = root;inOrder(root.right);}public Node treeToDoublyList(Node root) {inOrder(root);if(head != null){head.left = end;end.right = head;}return head;}
}
🚀 运行结果:

🕔 复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n),其中
n为二叉树的节点数,中序遍历需要访问所有节点。 - 空间复杂度: O ( n ) O(n) O(n),最差情况下,即树退化为链表时,递归深度达到
n,系统使用 O ( n ) O(n) O(n) 栈空间。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:
(树) 剑指 Offer 36. 二叉搜索树与双向链表 ——【Leetcode每日一题】
❓ 剑指 Offer 36. 二叉搜索树与双向链表 难度:中等 输入一棵二叉搜索树,将该二叉搜索树转换成一个 排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为…...
TypeScript初学
文章转载:https://blog.csdn.net/weixin_46185369/article/details/121512287 写的很详细,适合初学者看看。 一、TypeScript是什么? 1.TypeScript简称:TS,是JavaScript的超集。简单来说就是:JS有的TS都有…...
C/C++预定义宏
MSVC文档: https://learn.microsoft.com/en-us/cpp/preprocessor/predefined-macros?viewmsvc-170 GCC文档: https://gcc.gnu.org/onlinedocs/gcc/Function-Names.html https://gcc.gnu.org/onlinedocs/cpp/Predefined-Macros.html 参考:…...
原型链污染挖掘(存储XSS)
服务XSS响应 将JSON content-type更改为HTML 在Express应用中使用 JSON内容类型响应 并反映一个JSON: app.use(bodyParser.json({type: application/json})); app.post(/, function(req, res){_.merge({}, req.body);res.send(req.body); }); 在这些情况下&…...
Chrome开发者工具介绍
Chrome开发者工具介绍 前言1 打开DevTools2 命令菜单3 Elements面板ConsoleJavaScript调试Network 前言 Chrome开发者工具是谷歌浏览器自带的一款开发者工具,它可以给开发者带来很大的便利。常用的开发者工具面板主要包含Elements面板、Console面板、Sources面板、…...
利用MMPose进行姿态估计(训练、测试全流程)
前言 MMPose是一款基于PyTorch的姿态分析开源工具箱,是OpenMMLab项目成员之一,主要特性: 支持多种人体姿态分析相关任务:2D多人姿态估计、2D手部姿态估计、动物关键点检测等等更高的精度和更快的速度:包括“自顶向下”…...
ROS2 编译含有自定义消息项目报错:msg/detail/header__struct.h: 没有那个文件或目录
项目场景: 当迁移ROS 1 项目到 ROS 2 时,有时候会遇到消息类型的变化和更新,消息类型可能需要进行一些调整以适应新的ROS 2要求。本文将介绍如何处理自定义消息中的Header字段,以确保项目能够顺利地适应ROS 2的消息类型定义。 问…...
线段树思想拆解(下篇)
线段树思想拆解(下篇) 上篇回顾 到这里我们已经处理好了初始化以及添加方法,接下来实现范围的 query 方法 public int query(int queryL, int queryR) {return query(queryL, queryR, 1, orgLength - 1, 1);}到此为止通过借助 sum 数组&…...
Containerd容器镜像管理
1. 轻量级容器管理工具 Containerd 2. Containerd的两种安装方式 3. Containerd容器镜像管理 4. Containerd数据持久化和网络管理 1、Containerd镜像管理 1.1 Containerd容器镜像管理命令 docker使用docker images命令管理镜像单机containerd使用ctr images命令管理镜像,con…...
Baumer工业相机堡盟工业相机如何通过BGAPI SDK获取相机当前数据吞吐量(C#)
Baumer工业相机堡盟工业相机如何通过BGAPISDK里函数来获取相机当前数据吞吐量(C#) Baumer工业相机Baumer工业相机的数据吞吐量的技术背景CameraExplorer如何查看相机吞吐量信息在BGAPI SDK里通过函数获取相机接口吞吐量 Baumer工业相机通过BGAPI SDK获取…...
Ubuntu服务器版配置wifi
最近把曾经不用的上网本安装了一个Ubuntu-Server版,当成服务器来用,因为家庭网络布线问题,只好用自带的WIFI来连接网络,Server版也没有什么图形化的管理工具,之后手动编辑配置文件了。 Server下面配置起来还是很方便的…...
Windows 主机的VMware 虚拟机访问 wsl-ubuntu 的 API 服务
Windows 主机的VMware 虚拟机访问 wsl-ubuntu 的 API 服务 0. 背景1. 设置2. 删除 0. 背景 需要从Windows 主机的VMware 虚拟机访问 wsl-ubuntu 的 API 服务。 1. 设置 Windows 主机的IP:192.168.31.20 wsl-ubuntu Ubuntu-22.04 的IP:172.29.211.52 &…...
【Spring】(一)Spring设计核心思想
文章目录 一、初识 Spring1.1 什么是 Spring1.2 什么是 容器1.3 什么是 IoC 二、对 IoC 的深入理解2.1 传统程序开发方式存在的问题2.2 控制反转式程序的开发2.3 对比总结 三、对 Spring IoC 的理解四、DI 的概念4.1 什么是 DI4.2 DI 与 IoC的关系 一、初识 Spring 1.1 什么是…...
chrome插件开发实例04-智能收藏夹
目录 功能说明 演示 源码下载 源代码 manifest.json popup.html popup.js background.js 功能说明 基于chrome插件...
iOS技术之 手机系统15.0之后 的 UITableView section header多22像素问题
iOS 15 的 UITableView又新增了一个新属性:sectionHeaderTopPadding 会给每一个section header 增加一个默认高度,当我们 使用 UITableViewStylePlain 初始化 UITableView的时候,就会发现,系统给section header增高了22像素。 解…...
Windows下安装Kafka(图文记录详细步骤)
Windows下安装Kafka Kafka简介一、Kafka安装前提安装Kafka之前,需要安装JDK、Zookeeper、Scala。1.1、JDK安装(version:1.8)1.1.1、JDK官网下载1.1.2、JDK网盘下载1.1.3、JDK安装 1.2、Zookeeper安装1.2.1、Zookeeper官网下载1.2.…...
linuxARM裸机学习笔记(3)----主频和时钟配置实验
引言:本文主要学习当前linux该如何去配置时钟频率,这也是重中之重。 系统时钟来源: 32.768KHz 晶振是 I.MX6U 的 RTC 时钟源, 24MHz 晶振是 I.MX6U 内核 和其它外设的时钟源 1. 7路PLL时钟源【都是从24MHZ的晶振PLL而来…...
防勒索病毒
随着勒索软件攻击在2023年的激增,网络安全已成为当今最重要的议题之一。根据区块链分析公司Chainaanalysis的最新报告,勒索软件攻击已成为唯一呈增长趋势的基于加密货币的犯罪行为,勒索金额更是比一年前增加了近1.758亿美元,达到4…...
剑指 Offer 53 - II. 0~n-1 中缺失的数字
力扣 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。 示例 1: 输入: [0,1,3] 输出: 2 示例 2: 输入: [0,1,2,3,4,5…...
vue2和vue3区别
vue2和vue3的区别有以下8点: 1、双向数据绑定原理不同; 2、是否支持碎片; 3、API类型不同; 4、定义数据变量和方法不同; 5、生命周期钩子函数不同; 6、父子传参不同; 7、指令与插槽不同&#x…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
