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元 推荐理由…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
