【Leecode】Leecode刷题之路第99天之恢复二叉搜索树
题目出处
99-恢复二叉搜索树-题目出处
题目描述
个人解法
思路:
todo
代码示例:(Java)
todo
复杂度分析
todo
官方解法
99-恢复二叉搜索树-官方解法
方法1:显式中序遍历
思路:
代码示例:(Java)
@Data
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution1 {public void recoverTree(TreeNode root) {List<Integer> nums = new ArrayList<Integer>();inorder(root, nums);int[] swapped = findTwoSwapped(nums);recover(root, 2, swapped[0], swapped[1]);}public void inorder(TreeNode root, List<Integer> nums) {if (root == null) {return;}inorder(root.left, nums);nums.add(root.val);inorder(root.right, nums);}public int[] findTwoSwapped(List<Integer> nums) {int n = nums.size();int index1 = -1, index2 = -1;for (int i = 0; i < n - 1; ++i) {if (nums.get(i + 1) < nums.get(i)) {index2 = i + 1;if (index1 == -1) {index1 = i;} else {break;}}}int x = nums.get(index1), y = nums.get(index2);return new int[]{x, y};}public void recover(TreeNode root, int count, int x, int y) {if (root != null) {if (root.val == x || root.val == y) {root.val = root.val == x ? y : x;if (--count == 0) {return;}}recover(root.right, count, x, y);recover(root.left, count, x, y);}}}
复杂度分析
- 时间复杂度:O(N),其中 N 为二叉搜索树的节点数。中序遍历需要 O(N) 的时间,判断两个交换节点在最好的情况下是 O(1),在最坏的情况下是 O(N),因此总时间复杂度为 O(N)。
- 空间复杂度:O(N)。我们需要用 nums 数组存储树的中序遍历列表。
方法2:隐式中序遍历
思路:
代码示例:(Java)
public class Solution2 {public void recoverTree(TreeNode root) {Deque<TreeNode> stack = new ArrayDeque<TreeNode>();TreeNode x = null, y = null, pred = null;while (!stack.isEmpty() || root != null) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();if (pred != null && root.val < pred.val) {y = root;if (x == null) {x = pred;} else {break;}}pred = root;root = root.right;}swap(x, y);}public void swap(TreeNode x, TreeNode y) {int tmp = x.val;x.val = y.val;y.val = tmp;}}
复杂度分析
- 时间复杂度:最坏情况下(即待交换节点为二叉搜索树最右侧的叶子节点)我们需要遍历整棵树,时间复杂度为 O(N),其中 N 为二叉搜索树的节点个数。
- 空间复杂度:O(H),其中 H 为二叉搜索树的高度。中序遍历的时候栈的深度取决于二叉搜索树的高度。
方法3:Morris 中序遍历
思路:
代码示例:(Java)
public class Solution3 {public void recoverTree(TreeNode root) {TreeNode x = null, y = null, pred = null, predecessor = null;while (root != null) {if (root.left != null) {// predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止predecessor = root.left;while (predecessor.right != null && predecessor.right != root) {predecessor = predecessor.right;}// 让 predecessor 的右指针指向 root,继续遍历左子树if (predecessor.right == null) {predecessor.right = root;root = root.left;}// 说明左子树已经访问完了,我们需要断开链接else {if (pred != null && root.val < pred.val) {y = root;if (x == null) {x = pred;}}pred = root;predecessor.right = null;root = root.right;}}// 如果没有左孩子,则直接访问右孩子else {if (pred != null && root.val < pred.val) {y = root;if (x == null) {x = pred;}}pred = root;root = root.right;}}swap(x, y);}public void swap(TreeNode x, TreeNode y) {int tmp = x.val;x.val = y.val;y.val = tmp;}}
复杂度分析
- 时间复杂度:O(N),其中 N 为二叉搜索树的高度。Morris 遍历中每个节点会被访问两次,因此总时间复杂度为 O(2N)=O(N)。
- 空间复杂度:O(1)。
考察知识点
1.二叉树的中序遍历
收获
Gitee源码位置
99-恢复二叉搜索树-源码
相关文章:
【Leecode】Leecode刷题之路第99天之恢复二叉搜索树
题目出处 99-恢复二叉搜索树-题目出处 题目描述 个人解法 思路: todo代码示例:(Java) todo复杂度分析 todo官方解法 99-恢复二叉搜索树-官方解法 方法1:显式中序遍历 思路: 代码示例:&…...
【从零开始入门unity游戏开发之——C#篇41】C#迭代器(Iterator)——自定义类实现 foreach 操作
文章目录 前言一、什么是迭代器?二、标准迭代器的实现方法1、自定义一个类CustomList2、让CustomList继承IEnumerable接口3、再继承IEnumerator接口4、完善迭代器功能5、**foreach遍历的本质**:6、在Reset方法里把光标复原 三、用yield return语法糖实现…...
运算符重载 - 自定义运算符行为
引言 C 是一种支持面向对象编程(OOP)的编程语言,它允许程序员通过运算符重载来自定义类的行为。运算符重载使得我们可以为自定义类型定义与内置类型相似的操作方式,从而使代码更加直观和易读。 本文将详细介绍 C 中的运算符重载…...
RabbitMQ-基本使用
RabbitMQ: One broker to queue them all | RabbitMQ 官方 安装到Docker中 docker run \-e RABBITMQ_DEFAULT_USERrabbit \-e RABBITMQ_DEFAULT_PASSrabbit \-v mq-plugins:/plugins \--name mq \--hostname mq \-p 15672:15672 \-p 5672:5672 \--network mynet\-d \rabbitmq:3…...
sklearn基础教程
sklearn,全称为Scikit-learn,是一个基于Python的开源机器学习库,广泛用于数据挖掘和数据分析。它建立在NumPy、SciPy和matplotlib这些科学计算库之上,提供了简单而高效的工具来解决各种机器学习问题。 安装 首先,确保…...
173. 矩阵距离 acwing -多路BFS
原题链接:173. 矩阵距离 - AcWing题库 给定一个 N行 M 列的 01矩阵 A,A[i][j] 与 A[k][l]]之间的曼哈顿距离定义为: dist(i,j,k,l)|i−k||j−l|| 输出一个 N 行 M 列的整数矩阵 B,其中: B[i][j]min1≤x≤N,1≤y≤M,A…...
【MySQL】--- 内置函数
Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏: MySQL 🏠 时间函数 约定:我们在MySQL中说的日期指的是年 月 日,时间指的是时 分 秒。 🧷 now() select n…...
更改element-plus的table样式
表头样式: <el-table :data"props.tableData" style"width: 100%" :header-cell-style"headerCellStyle" :cell-style"cellStyle"> </el-table>样式: // 表头样式 const headerCellStyle {backgro…...
25.Java JUC 引入(进程与线程、线程的状态、并发与并行、管程、用户线程与守护线程)
一、JUC 简介 JUC 是 java.util.concurrent 工具包的简称,这是一个处理线程的工具包,从 JDK1.5 开始出现 二、进程与线程 1、基本介绍 (1)进程 进程是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源…...
双目视觉:reprojectImageTo3D函数
前言 reprojectImageTo3D 是 OpenCV 中用于从视差图生成三维点云的函数。它的原理是利用视差图和相机的校准参数,通过三角测量法,计算每个像素对应的三维坐标。以下内容根据源码分析所写,觉得可以的话,点赞收藏哈!&am…...
深度解析 Kubernetes Service 负载均衡器及其在 Cube Studio 推理服务中的优化选择
目录 一、Kubernetes Service 负载均衡器概述 Service 的核心功能: 二、Kubernetes Service 类型及适用场景 1. ClusterIP(默认类型) 2. NodePort 3. LoadBalancer 4. ExternalName 5. Ingress(增强型 Service)…...
NLP 中文拼写检测纠正论文-07-NLPTEA-2020中文语法错误诊断共享任务概述
拼写纠正系列 NLP 中文拼写检测实现思路 NLP 中文拼写检测纠正算法整理 NLP 英文拼写算法,如果提升 100W 倍的性能? NLP 中文拼写检测纠正 Paper java 实现中英文拼写检查和错误纠正?可我只会写 CRUD 啊! 一个提升英文单词拼…...
快速上手LangChain(三)构建检索增强生成(RAG)应用
文章目录 快速上手LangChain(三)构建检索增强生成(RAG)应用概述索引阿里嵌入模型 Embedding检索和生成RAG应用(demo:根据我的博客主页,分析一下我的技术栈)快速上手LangChain(三)构建检索增强生成(RAG)应用 langchain官方文档:https://python.langchain.ac.cn/do…...
深度学习中的离群值
文章目录 深度学习中有离群值吗?深度学习中的离群值来源:处理离群值的策略:1. 数据预处理阶段:2. 数据增强和鲁棒模型:3. 模型训练阶段:4. 异常检测集成模型: 如何处理对抗样本?总结…...
汽车燃油软件标定测试
油箱测试 确定油箱的参数: 总容积,额定容积,不可用容积等。油泵测试(静态) 分为加油测试,减油测试,1L或者500ml增减; 分别测试油泵的阻值输出,类似: 油量 阻…...
#C02L02P01. C02.L02.一维数组最值问题.知识点1.求最大值
从键盘读入n(1<n<100)个正整数,输出最大值。 算法分析 假设一个最大值 maxx0 ; maxx 依次跟数组中的元素进行比较; 如果该数组元素大于 maxx ,则将该数组元素值赋值给 maxx ; maxx 即…...
pycharm如何拉取一个git项目,然后,修改后再上传到自建的项目中?
以chattts为例 https://github.com/2noise/ChatTTS.git 1.建一个虚拟环境,用于项目使用 2.pycharm新建工程 3.忽略 提示 勾选,新建远程仓库 设置账号和密码 设置git路径,一般是正确的,点测试即可 &…...
【数据库初阶】MySQL中表的约束(上)
🎉博主首页: 有趣的中国人 🎉专栏首页: 数据库初阶 🎉其它专栏: C初阶 | C进阶 | 初阶数据结构 亲爱的小伙伴们,大家好!在这篇文章中,我们将深入浅出地为大家讲解 MySQL…...
smbms超市管理系统
系统测试及实现效果 完整源码已上传资源 登录界面 系统首页 订单管理页面 用户管理页面 供应商管理页面 密码修改 SQL语句分析 存储引擎:InnoDB,支持事务和外键;字符集:utf8,支持多语言字符;排序规则&am…...
Visual Studio 中增加的AI功能
前言: 人工智能的发展,在现在,编程技术的IDE里面也融合了AI的基本操做。本例,以微软的Visual Studio中的人工智能的功能介绍例子。 本例的环境: Visual Studio 17.12 1 AI 智能变量检测: 上图展示了一…...
大功率PCB设计
1.电源和电机的走线用线径较大的铺铜,讲究的是走线顺畅: 2.同一个电源属性四层板都铺铜,并打很多过孔: 3.走线顺畅,可以看到从左到右供电。从右向左接地,加电流采样: 一个问题,这样会形成电源环…...
Nginx与frp结合实现局域网和公网的双重https服务
背景: 因为局域网内架设了 tiddlywiki、 Nextcloud 等服务,同时也把公司的网站架设在了本地,为了实现局域网直接在局域网内访问,而外部访问通过frps服务器作为反向代理的目的,才有此内容。 实现的效果如下图琐事 不喜欢…...
改投论文时如何重构
摘要: 不同期刊和会议对于论文的风格、页数限制等方面有一些差别, 论文在某个地方被拒, 改投别处时需要进行重构. 本贴描述重构的基本方案. 你的衣柜乱糟糟的, 如何清理呢? 方案 A. 把不喜欢的衣服一件件丢掉.方案 B. 把衣服全部丢出来, 然后再把喜欢的衣服一件件放进去. 对…...
【YOLOv5】源码(common.py)
该文件位于/models/common.py,提供了构建YOLOv5模型的各种基础模块,其中包含了常用的功能模块,如自动填充autopad函数、标准卷积层Conv、瓶颈层Bottleneck、C3、SPPF、Concat层等 参考笔记:【YOLOv3】 源码(common.py…...
python中的赋值方法
python赋值方法有很多,主要可以分为链式赋值、系列解包赋值、常量形式赋值,下面介绍下三者间区别: 1、链式赋值: 链式赋值用于同一个对象赋值给多个变量 xy123 可以认为是 x 123 y 123 2、系列解包赋值: 系列数据…...
pyhton 掩码 筛选显示
目录 bitwise_and控制: 点乘: 性能对比: bitwise_and控制: import cv2# 读取彩色图和mask二值图 color_img cv2.imread(color_image.jpg) mask cv2.imread(mask.jpg, 0) # 以灰度模式读取二值图# 确保彩色图和mask的尺寸一…...
测试覆盖率
1、概念 覆盖率测试,也称为测试覆盖率分析,是软件测试中的一个重要概念,用来衡量测试用例执行时对代码的覆盖程度。它提供了一种量化的方法来评估测试集的充分性,即测试是否足够广泛地触及了应用程序的所有部分。覆盖率测试可以应…...
clickhouse query_log 常用查询语句
1、查询一段时间耗时超过3秒的语句。 SELECT* FROMsystem.query_log WHEREquery_duration_ms > 30000AND event_time > 2024-12-31 15:50:00 AND event_time < 2024-12-31 17:50:00 ORDER BYevent_time desc;2、查询一段时间报错的语句 SELECT* FROMsystem.query_lo…...
uni-app 资源引用(绝对路径和相对路径)方法汇总
文章目录 一、前言🍃二、绝对路径和相对路径2.1 绝对路径2.2 相对路径 三、引用组件四、引用js4.1 js 文件引入4.2 NPM支持 五、引用css六、引用json6.1 json文件引入 七、引用静态资源7.1 模板内引入静态资源7.2 css 引入静态资源7.3 js/uts 引入静态资源7.4 静态资…...
Java SpringBoot使用EasyExcel导入导出Excel文件
点击下载《Java SpringBoot使用EasyExcel导入导出Excel文件(源代码)》 在 Java Spring Boot 项目中,导入(读取)和导出(写入) Excel 文件是一项常见的需求。EasyExcel 是阿里巴巴开源的一个用于简化 Java 环境下 Excel…...
CDN SSLTLS以及安全
随着互联网的发展,内容分发网络(CDN)在提升网站访问速度和安全性方面发挥了重要作用。然而,CDN在带来便利的同时也面临一些安全挑战。本文将探讨CDN的安全风险,并深入解析SSL/TLS加密技术及其在CDN中的应用。 CDN的安全…...
安卓11 SysteUI添加按钮以及下拉状态栏的色温调节按钮
最近客户想要做一个台灯产品,需要实现 串口调节台灯功能 ,其中包括 亮度调节 色温调节 开关 三个功能 话不多说,贴代码 diff --git a/packages/SystemUI/AndroidManifest.xml b/packages/SystemUI/AndroidManifest.xml old mode 100644 new …...
SpringMVC启动与请求处理流程解析
目录 SpringMVC的基本结构 1.MVC简介 2.基本结构 什么是Handler? 什么是HandlerMapping? 什么是HandlerAdapter? RequestMapping方法参数解析 DispatcherServlet的init()方法 DispatcherServlet的doService()方法 SpringBoot整合SpringMVC …...
RabbitMQ案例
1. 导入依赖 <!--AMQP依赖,包含RabbitMQ--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId></dependency> 发送消息 注入RabbitTemplate Autowired RabbitT…...
前路漫漫,曙光在望 !
起始 从20年大一开始写作至今,转眼五年时光已经过去了,最开始在CSDN这个平台写博客也只是因为一次机缘巧合情况下得知写博客可以获取奖赏,所以那个时期开始疯狂在CSDN发文记录自己编程学习过程,但是至今也未从写作中获利一分哈…...
音视频-----RTSP协议 音视频编解码
流媒体协议详解:RTSP、RTP、RTCP、SIP、SDP、RTMP、WebRTC、WebSocket-CSDN博客 上文讲解比较清楚 多媒体编解码基础知识 一文详解WebRTC、RTSP、RTMP、SRT-腾讯云开发者社区-腾讯云 RTP :(Real-time Transport Protocol)是用于Internet上针对多媒体数据流的一种传…...
SpringMVC的消息转换器
SpringMVC的消息转换器(Message Converter)是Spring框架中用于处理HTTP请求和响应体与Java对象之间转换的组件。它们使得开发人员可以轻松地将HTTP请求的数据映射到方法参数,并将返回的对象转换为HTTP响应。 工作原理 当一个HTTP请求到达Spr…...
计算机网络练习题
学习这么多啦,那就简单写几个选择题巩固一下吧! 1. 在IPv4分组各字段中,以下最适合携带隐藏信息的是(D) A、源IP地址 B、版本 C、TTL D、标识 2. OSI 参考模型中,数据链路层的主要功能是(…...
本地测试文件解析
PostMapping("/test") public void test() throws IOException {Path csvFile Paths.get("D:\\test/27.csv");//虚拟机退出时删除临时文件csvFile.toFile().deleteOnExit();List<String> list Files.readAllLines(csvFile, Charset.forName("…...
websocket-sharp:.NET平台上的WebSocket客户端与服务器开源库
推荐一个C#开发的,实现WebSocket功能的开源项目。 01 项目简介 websocket-sharp提供 WebSocket 客户端和服务器库,基于 C# 开发的,并遵循 WebSocket 协议规范,使得开发人员能够轻松地在 .NET 应用程序中实现 WebSocket 通信。 …...
SwiftUI 撸码常见错误 2 例漫谈
概述 在 SwiftUI 日常撸码过程中,头发尚且还算茂盛的小码农们经常会犯这样那样的错误。虽然犯这些错的原因都很简单,但有时想要快速准确的定位它们却并不容易。 况且这些错误还可能在模拟器和 Xcode 预览(Preview)表现的行为不甚…...
回归预测 | MATLAB实现CNN-GRU卷积门控循环单元多输入单输出回归预测
回归预测 | MATLAB实现CNN-GRU卷积门控循环单元多输入单输出回归预测 目录 回归预测 | MATLAB实现CNN-GRU卷积门控循环单元多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现CNN-GRU卷积门控循环单元多输入单输出回归预测 数据准备&#x…...
Nginx常用配置之详解(Detailed Explanation of Common Nginx Configurations)
Nginx常用配置详解(图文全面总结) Nginx Nginx 是一款轻量级的高性能 HTTP、 和反向代理服务器。 Nginx,被广泛用于负载均衡、静态文件服务、和代理.........等。 Nginx,以高并发、低内存占用、和高可用性著称,大部分的大厂以及公司都在使…...
【PyTorch入门】 PyTorch不同优化器的比较
本次分享pytorch中几种常用的优化器,并进行互相比较。 PyTorch 优化器原理及优缺点分析 在 PyTorch 中,torch.optim 提供了多种优化器用于神经网络训练。每种优化器背后有不同的更新规则和机制,旨在适应不同的训练需求。以下是五种常见优化器…...
jest使用__mocks__设置模拟函数不生效 解决方案
模拟文件 // __mocks__/axios.js const axios jest.fn(); axios.get jest.fn(); axios.get.mockResolvedValue({data: {undoList: [get data],}, }); export default axios; 测试文件 jest.mock(axios); import Axios from axios;test(mytest, () > {console.log("…...
聆听音乐 1.5.9 | 畅听全网音乐,支持无损音质下载
聆听音乐手机版是面向广大音乐爱好者的移动应用程序,用户可以随时随地通过手机享受丰富的音乐资源。它提供了多种魅力功能,让用户在手机上畅享更舒适的音乐体验,每位用户都能享受精彩纷呈的收听体验。此外,软件还支持无损音质音乐…...
VMware去虚拟化
介绍两款用于去除VMware虚拟机虚拟化特征的工具,这些工具可以帮助用户在虚拟机中运行游戏时避免被游戏检测到虚拟机环境,从而防止游戏因检测到虚拟机而闪退。这些工具通过修改虚拟机的硬件信息(如硬盘、声卡、网卡、主板芯片组、显卡、主板信…...
汉王扫描王 2.9.16 |免费无广告的智能扫描软件,支持多种格式导出
汉王扫描王是一款功能全面的智能扫描软件,集成了文字识别、表格提取和文档转换等功能。它支持将文档转换为PDF、Word、Excel等多种格式,非常适合学生、教师、业务人员和财务工作者使用。该软件具备手机扫描仪功能,能够自动抠边、矫正文档&…...
毕设中所学
1、交叉引用 在毕业设计论文Word中交叉引用参考文献_交叉引用如何标注[1~6]-CSDN博客 另:将标号或其他文字改为上标的快捷键是CtrlShift。 图的交叉引用一样,修改引用类型即可。 2、ENVI安装 ENVI5.6 安装教程,新手入门(超详细…...
[微服务]分布式搜索Java客户端
快速入门 使用RestClient客户端进行数据搜索可以分为两步 构建并发起请求 代码解读: 第一步,创建SearchRequest对象,指定索引库名第二步,利用request.source()构建DSL,DSL中可以包含查询、分页、排序、高亮等 query…...