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

(树) 剑指 Offer 36. 二叉搜索树与双向链表 ——【Leetcode每日一题】

❓ 剑指 Offer 36. 二叉搜索树与双向链表

难度:中等

输入一棵二叉搜索树,将该二叉搜索树转换成一个 排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

为了让您更好地理解问题,以下面的二叉搜索树为例:
在这里插入图片描述
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

在这里插入图片描述
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意:此题对比原题有改动。

💡思路:中序递归遍历

由二叉搜索树的性质:中序遍历即为 递增序列。所以可以在中序遍历的时候完成双向链表的转化:

定义两个结点 headend 分别指向已转换链表的 头结点尾结点

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…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

centos 7 部署awstats 网站访问检测

一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...

条件运算符

C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...