Leetcode力扣秋招刷题路-0099
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结
99. 恢复二叉搜索树
给你二叉搜索树的根节点 root ,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。
示例 1:

输入:root = [1,3,null,null,2]
输出:[3,1,null,null,2]
解释:3 不能是 1 的左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2:

输入:root = [3,1,4,null,null,2]
输出:[2,1,4,null,null,3]
解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示:
树上节点的数目在范围 [2, 1000] 内
−231-2^{31}−231 <= Node.val <= 231−12^{31} - 1231−1
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗?
思路
因为只有两个节点错误,所以只要找出这两个节点然后交换值即可。
BST中序遍历是升序结果,因此进行中序遍历,使用三个指针指示节点,cur为当前节点,pre为当前节点之前的节点,wrongNode为错误节点
当当前节点小于上一个节点时,上一个节点pre就是第一个错误节点,用wrongNode记录,然后继续遍历,找出第二个错误节点, 这里有两种情况:
1.当当前节点大于wrongNode时,它的前节点就是第二个错误节点,如[1,3,2,4],错误节点分别为3、2
2.遍历结束时仍然没有节点大于wrongNode,则最后一个节点就是错误节点,如[3,1,2],错误节点为3、2
public void recoverTree(TreeNode root) {if (root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode pre = null, cur = root, wrongNode = null;while (!stack.isEmpty() || cur != null) {if (cur != null) {stack.add(cur);cur = cur.left;} else {cur = stack.pop();//与上一个节点比较,找到错误节点if (wrongNode == null && pre != null && cur.val < pre.val) {wrongNode = pre;}//表示当前节点是否大于wrongNodeif (wrongNode != null && cur.val > wrongNode.val) {swap(pre, wrongNode);break;}pre = cur;cur = cur.right;}}//如果没有节点大于wrongNode,与最后一个节点交换值if (wrongNode != null && wrongNode.val > pre.val) {swap(pre, wrongNode);}
}private void swap(TreeNode pre, TreeNode wrongNode) {int tmp = pre.val;pre.val = wrongNode.val;wrongNode.val = tmp;
}
相关文章:
Leetcode力扣秋招刷题路-0099
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 99. 恢复二叉搜索树 给你二叉搜索树的根节点 root ,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。 示例 1: 输入…...
消费升级趋势下,平台如何在广告电商模式中攫取新流量
如今电商平台飞速发展,越来越多的人加入电商运营的行列,同行竞争逐渐变得激烈起来,为了能够让平台有更多的展现机会,提升平台的商品转化率,大家都很重视平台的优化,因为一个好的平台可以给自身带来更多的流…...
华为OD机试真题 用 C++ 实现 - 众数和中位数 | 多看题,提高通过率
最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…...
Linux NOR 开发指南
Linux NOR 开发指南 1 简介 编写目的 此文档描述Sunxi NOR 模块的使用方法,为相关人员调试提供指导 适用范围 boot0: 适用于brandy-2.0u-boot: 适用于u-boot-2018kernel: 适用于linux-4.9/linux-5.4 内核 BSP 的开发人员、测试人员 2 模块介绍 2.1 模块功能…...
免费领取丨精算与金融建模行业解决方案白皮书,不要错过!
一、我国精算行业现状 精算学是对人类社会所面临的各种风险及其他客观事务进行量化分析和处理的一门科学。在保险、金融、投资和各类风险管理等许多领域得到广泛应用,尤其在保险和社会保障领域,已成为不可或缺的科学和技术,以保险公司为例&a…...
ideal创建maven项目
前置工作本机安装mavenIdea 设置使用本机maven 工具Settings--->Maven开始创建maven项目创建maven项目,勾选通过模板创建,选择 maven-archetype-webapp 模板GroupId: 公司名倒序ArtifactId: 项目名设置本地maven仓库配置项目文件显示名,和…...
ChatGPT是什么?为何会引爆国内算力需求?
过去十年中,通过“深度学习大算力”从而获得训练模型是实现人工智能的主流技术途径。由于深度学习、数据和算力这三个要素都已具备,全世界掀起了“大炼模型”的热潮,也催生了大批人工智能企业。大模型是人工智能的发展趋势和未来大模型&#…...
【Linux】进程间通信(万字详解)—— 匿名管道 | 命名管道 | System V | 共享内存
🌈欢迎来到Linux专栏~~进程通信 (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort目前状态:大三非科班啃C中🌍博客主页:张小姐的猫~江湖背景快上车🚘,握好方向盘跟我有一起打天下嘞!送给自己的一句鸡汤…...
【Database-02】达梦数据库 - DM Manager管理工具安装
1、简介 DM Manager是达梦数据库自带的图形化界面管理工具,在安装达梦数据库的时候就会自动安装。 Linux环境,默认安装路径为:达梦安装目录/tool/manager,如果Linux是安装GUI,那么就可以直接启动使用。 实际大部分使…...
剑指 Offer 42. 连续子数组的最大和
剑指 Offer 42. 连续子数组的最大和 难度:easy\color{Green}{easy}easy 题目描述 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输…...
双指针 (C/C++)
1. 双指针 双指针算法的核心思想:将暴力解法的时间复杂度,通常是O(N*N),通过某种特殊的性质优化到O(N)。 做题思路:先想想暴力解法的思路,然后分析这道题的特殊性质,一般是单调性。然后得出双指针算法的思路…...
CVE-2023-23752 Joomla未授权访问漏洞分析
漏洞概要 Joomla 在海外使用较多,是一套使用 PHP 和 MySQL 开发的开源、跨平台的内容管理系统(CMS)。 Joomla 4.0.0 至 4.2.7 版本中的 ApiRouter.php#parseApiRoute 在处理用户的 Get 请求时未对请求参数有效过滤,导致攻击者可向 Joomla 服务端点发送包…...
单通道说话人语音分离——Conv-TasNet(Convolutional Time-domain audio separation Network)
单通道说话人语音分离——Conv-TasNet模型(Convolutional Time-domain audio separation Network) 参考文献:《Conv-TasNet: Surpassing Ideal Time-FrequencyMagnitude Masking for Speech Separation》 1.背景 在真实的声学环境中,鲁棒的语音处理通常…...
华为OD机试真题Python实现【环中最长子串】真题+解题思路+代码(20222023)
环中最长子串 题目 给你一个字符串s,首尾相连成一个环形, 请你在环中找出o字符出现了偶数次最长子字符串的长度. 备注: 1 <= s.lenth <= 5x10^5 s只包含小写英文字母 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Python)真题目录汇总 ## 输入 输入是…...
Netcat安装与使用(nc)
Netcat安装与使用1.Netcat简介1.1.Netcat安装1.1.1.安装整体流程1.1.1.1.安装依赖1.1.1.2.安装Netcat1.1.1.3.配置环境变量1.1.1.4.测试1.2.Netcat基本功能1.3.Netcat常用参数2.Netcat用法2.1.前期准备2.2.banner相关信息抓取2.3.端口扫描2.3.1.扫描指定端口2.3.2.扫描指定端口…...
蓝桥杯:聪明的猴子
题目链接:聪明的猴子https://www.lanqiao.cn/problems/862/learning/ 目录 题目描述 输入描述 输出描述 输入输出样例 运行限制 解题思路: 最小生成树 AC代码(Java): 课后练习: 题目描述 在一个热带雨林中生存…...
Spring Boot应用如何快速接入Prometheus监控
1. Micrometer简介Micrometer为Java平台上的性能数据收集提供了一个通用的API,它提供了多种度量指标类型(Timers、Guauges、Counters等),同时支持接入不同的监控系统,例如Influxdb、Graphite、Prometheus等。可以通过M…...
vscode远程调试python
目的 注意:这里我们想要实现的是:用vscode 使用remote ssh打开project,然后直接在project里面进行debug,而不需要 在本地vscode目录打开一样的project。 假设大家已经会使用remote ssh打开远程服务器的代码了,那么只…...
Spring Boot 框架 集成 Knife4j(内含源代码)
Spring Boot 框架 集成 Knife4j(内含源代码) 源代码下载链接地址:https://download.csdn.net/download/weixin_46411355/87480176 目录Spring Boot 框架 集成 Knife4j(内含源代码)源代码下载链接地址:[htt…...
什么蓝牙耳机适合打游戏?打游戏不延迟的蓝牙耳机
为了提升游戏体验,除了配置强悍的主机外,与之搭配蓝牙耳机等外设产品也尤为重要,今天就带大家来了解一下以下几款适合玩游戏,低延迟操作的蓝牙耳机。 第一款:南卡小音舱蓝牙耳机 参考价格:239元 推荐理由…...
力扣第97题:多数元素
第一部分:问题描述 给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入:nums = [3,2,3] 输出:3 示例 2: 输入:nums = [2,2,1,1,1…...
5分钟快速上手:用Docker一键部署Milvus向量数据库(附常见错误解决)
5分钟极速部署Milvus:Docker实战指南与高频避坑手册 当我们需要快速验证一个AI项目的可行性时,最头疼的往往不是模型本身,而是基础设施的搭建。上周我正准备测试一个图像检索系统,结果在向量数据库部署环节就卡了整整两天——各种…...
2026届最火的六大降AI率网站实际效果
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 想要把AI生成内容被检测出来的可能性降低,得从好多方面着手,重点留意…...
C#开发者必看:INIFileParser库解决INI配置文件乱码问题的实战指南
C#开发者必看:INIFileParser库解决INI配置文件乱码问题的实战指南 在Windows应用开发中,INI文件作为一种轻量级配置存储格式,至今仍被广泛使用。但许多C#开发者发现,当配置文件路径包含中文、空格或特殊字符时,传统的W…...
避坑指南:用Docker部署Oracle 11g时你一定会遇到的5个权限问题(附终极解决方案)
避坑指南:用Docker部署Oracle 11g时你一定会遇到的5个权限问题(附终极解决方案) 在容器化技术席卷全球的今天,Docker已成为部署数据库的首选工具之一。然而,当我们将Oracle 11g这样的传统数据库巨人塞进轻量级容器时&a…...
5步打造Xbox 360游戏PC运行环境:Xenia Canary模拟器全攻略
5步打造Xbox 360游戏PC运行环境:Xenia Canary模拟器全攻略 【免费下载链接】xenia-canary Xbox 360 Emulator Research Project 项目地址: https://gitcode.com/gh_mirrors/xe/xenia-canary Xenia Canary作为领先的Xbox 360开源模拟器,通过精准的…...
SYNBO 已上线 BitMart 交易所,Synbo Camp 同步开启
2026年3月31日,Synbo.io 原生代币 SYNBO 将上线 BitMart 交易所,这也成为 Synbo 发展进程中的又一里程碑,并同步开启 Synbo Camp 招募活动。这不仅是一次产品上线与活动发布,更标志着 Synbo 正式向行业递交一套关于未来融资协作方…...
[技术突破] 移动高精度定位新纪元:Android平台RTKLIB解决方案全解析
[技术突破] 移动高精度定位新纪元:Android平台RTKLIB解决方案全解析 【免费下载链接】RtkGps Playing with rtklib on android 项目地址: https://gitcode.com/gh_mirrors/rt/RtkGps 技术原理篇:核心算法与协议支持 解锁厘米级定位:R…...
告别答辩 PPT 加班地狱!Paperxie AI PPT,一键生成本科生专属高分答辩模板
paperxie-免费查重复率aigc检测/开题报告/毕业论文/智能排版/文献综述/AIPPThttps://www.paperxie.cn/ppt/createhttps://www.paperxie.cn/ppt/create 一、本科生的答辩 PPT 困局:为什么你熬到三点还在改? 毕业论文写完的那一刻,以为终于能松…...
用Python和Keras从零搭建疲劳驾驶检测器:MTCNN人脸对齐与CNN分类实战
用Python和Keras从零搭建疲劳驾驶检测器:MTCNN人脸对齐与CNN分类实战 在智能交通领域,驾驶员状态监测正成为保障道路安全的关键技术。本文将带您从零构建一个基于视觉分析的疲劳检测系统,通过MTCNN实现毫秒级人脸对齐,结合自定义C…...
