(树) 剑指 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…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
