(树) 剑指 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…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
