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

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} - 12311

进阶:使用 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开始的秋招刷题路&#xff0c;记录下所刷每道题的题解&#xff0c;帮助自己回顾总结 99. 恢复二叉搜索树 给你二叉搜索树的根节点 root &#xff0c;该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下&#xff0c;恢复这棵树 。 示例 1&#xff1a; 输入…...

消费升级趋势下,平台如何在广告电商模式中攫取新流量

如今电商平台飞速发展&#xff0c;越来越多的人加入电商运营的行列&#xff0c;同行竞争逐渐变得激烈起来&#xff0c;为了能够让平台有更多的展现机会&#xff0c;提升平台的商品转化率&#xff0c;大家都很重视平台的优化&#xff0c;因为一个好的平台可以给自身带来更多的流…...

华为OD机试真题 用 C++ 实现 - 众数和中位数 | 多看题,提高通过率

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…...

Linux NOR 开发指南

Linux NOR 开发指南 1 简介 编写目的 此文档描述Sunxi NOR 模块的使用方法&#xff0c;为相关人员调试提供指导 适用范围 boot0: 适用于brandy-2.0u-boot: 适用于u-boot-2018kernel: 适用于linux-4.9/linux-5.4 内核 BSP 的开发人员、测试人员 2 模块介绍 2.1 模块功能…...

免费领取丨精算与金融建模行业解决方案白皮书,不要错过!

一、我国精算行业现状 精算学是对人类社会所面临的各种风险及其他客观事务进行量化分析和处理的一门科学。在保险、金融、投资和各类风险管理等许多领域得到广泛应用&#xff0c;尤其在保险和社会保障领域&#xff0c;已成为不可或缺的科学和技术&#xff0c;以保险公司为例&a…...

ideal创建maven项目

前置工作本机安装mavenIdea 设置使用本机maven 工具Settings--->Maven开始创建maven项目创建maven项目&#xff0c;勾选通过模板创建&#xff0c;选择 maven-archetype-webapp 模板GroupId: 公司名倒序ArtifactId: 项目名设置本地maven仓库配置项目文件显示名&#xff0c;和…...

ChatGPT是什么?为何会引爆国内算力需求?

过去十年中&#xff0c;通过“深度学习大算力”从而获得训练模型是实现人工智能的主流技术途径。由于深度学习、数据和算力这三个要素都已具备&#xff0c;全世界掀起了“大炼模型”的热潮&#xff0c;也催生了大批人工智能企业。大模型是人工智能的发展趋势和未来大模型&#…...

【Linux】进程间通信(万字详解)—— 匿名管道 | 命名管道 | System V | 共享内存

&#x1f308;欢迎来到Linux专栏~~进程通信 (꒪ꇴ꒪(꒪ꇴ꒪ )&#x1f423;,我是Scort目前状态&#xff1a;大三非科班啃C中&#x1f30d;博客主页&#xff1a;张小姐的猫~江湖背景快上车&#x1f698;&#xff0c;握好方向盘跟我有一起打天下嘞&#xff01;送给自己的一句鸡汤…...

【Database-02】达梦数据库 - DM Manager管理工具安装

1、简介 DM Manager是达梦数据库自带的图形化界面管理工具&#xff0c;在安装达梦数据库的时候就会自动安装。 Linux环境&#xff0c;默认安装路径为&#xff1a;达梦安装目录/tool/manager&#xff0c;如果Linux是安装GUI&#xff0c;那么就可以直接启动使用。 实际大部分使…...

剑指 Offer 42. 连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 输入一个整型数组&#xff0c;数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输…...

双指针 (C/C++)

1. 双指针 双指针算法的核心思想&#xff1a;将暴力解法的时间复杂度&#xff0c;通常是O(N*N)&#xff0c;通过某种特殊的性质优化到O(N)。 做题思路&#xff1a;先想想暴力解法的思路&#xff0c;然后分析这道题的特殊性质&#xff0c;一般是单调性。然后得出双指针算法的思路…...

CVE-2023-23752 Joomla未授权访问漏洞分析

漏洞概要 Joomla 在海外使用较多&#xff0c;是一套使用 PHP 和 MySQL 开发的开源、跨平台的内容管理系统(CMS)。 Joomla 4.0.0 至 4.2.7 版本中的 ApiRouter.php#parseApiRoute 在处理用户的 Get 请求时未对请求参数有效过滤&#xff0c;导致攻击者可向 Joomla 服务端点发送包…...

单通道说话人语音分离——Conv-TasNet(Convolutional Time-domain audio separation Network)

单通道说话人语音分离——Conv-TasNet模型(Convolutional Time-domain audio separation Network) 参考文献&#xff1a;《Conv-TasNet: Surpassing Ideal Time-FrequencyMagnitude Masking for Speech Separation》 1.背景 在真实的声学环境中&#xff0c;鲁棒的语音处理通常…...

华为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.扫描指定端口…...

蓝桥杯:聪明的猴子

题目链接&#xff1a;聪明的猴子https://www.lanqiao.cn/problems/862/learning/ 目录 题目描述 输入描述 输出描述 输入输出样例 运行限制 解题思路&#xff1a; 最小生成树 AC代码&#xff08;Java&#xff09;: 课后练习&#xff1a; 题目描述 在一个热带雨林中生存…...

Spring Boot应用如何快速接入Prometheus监控

1. Micrometer简介Micrometer为Java平台上的性能数据收集提供了一个通用的API&#xff0c;它提供了多种度量指标类型&#xff08;Timers、Guauges、Counters等&#xff09;&#xff0c;同时支持接入不同的监控系统&#xff0c;例如Influxdb、Graphite、Prometheus等。可以通过M…...

vscode远程调试python

目的 注意&#xff1a;这里我们想要实现的是&#xff1a;用vscode 使用remote ssh打开project&#xff0c;然后直接在project里面进行debug&#xff0c;而不需要 在本地vscode目录打开一样的project。 假设大家已经会使用remote ssh打开远程服务器的代码了&#xff0c;那么只…...

Spring Boot 框架 集成 Knife4j(内含源代码)

Spring Boot 框架 集成 Knife4j&#xff08;内含源代码&#xff09; 源代码下载链接地址&#xff1a;https://download.csdn.net/download/weixin_46411355/87480176 目录Spring Boot 框架 集成 Knife4j&#xff08;内含源代码&#xff09;源代码下载链接地址&#xff1a;[htt…...

什么蓝牙耳机适合打游戏?打游戏不延迟的蓝牙耳机

为了提升游戏体验&#xff0c;除了配置强悍的主机外&#xff0c;与之搭配蓝牙耳机等外设产品也尤为重要&#xff0c;今天就带大家来了解一下以下几款适合玩游戏&#xff0c;低延迟操作的蓝牙耳机。 第一款&#xff1a;南卡小音舱蓝牙耳机 参考价格&#xff1a;239元 推荐理由…...

C++编译产物为何在边缘端频繁触发OOM?深度解析.lto、.eh_frame、.comment段的隐藏开销(含Bloaty对比报告)

第一章&#xff1a;C编译产物在边缘端触发OOM的根本动因边缘设备普遍受限于物理内存&#xff08;如 512MB–2GB RAM&#xff09;、无 Swap 分区、缺乏内存过载保护机制&#xff0c;而现代 C 编译器&#xff08;如 GCC 11/Clang 14&#xff09;默认启用的优化策略与运行时特性&a…...

告别排版地狱:PaperXie AI,10 分钟让你的毕业论文合规 “零返工”

paperxie-免费查重复率aigc检测/开题报告/毕业论文/智能排版/文献综述/AIPPThttps://www.paperxie.cn/format/typesettinghttps://www.paperxie.cn/format/typesetting 引言&#xff1a;被格式细节毁掉的毕业努力 当你熬了无数个夜晚&#xff0c;反复打磨论文的每一个论点&…...

鸿蒙物联网开发教程-第八章 网络请求1

第八章 网络请求 8.1 网络请求概述 鸿蒙应用中的网络请求主要使用fetch API或@ohos.net.http模块进行网络通信。网络请求用于: 获取远程数据 上传数据到服务器 与物联网平台通信 调用第三方API 8.2 HTTP请求 8.2.1 使用fetch API // 发送GET请求fetch(‘https://api.e…...

3大突破!网盘下载加速工具让你的文件获取效率倍增

3大突破&#xff01;网盘下载加速工具让你的文件获取效率倍增 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移动云盘 / 天翼云盘…...

3大维度解锁BG3 Mod Manager潜能:构建高效博德之门3模组管理体系

3大维度解锁BG3 Mod Manager潜能&#xff1a;构建高效博德之门3模组管理体系 【免费下载链接】BG3ModManager A mod manager for Baldurs Gate 3. This is the only official source! 项目地址: https://gitcode.com/gh_mirrors/bg/BG3ModManager 价值定位&#xff1a;重…...

让AI学习最优抓取:基于快马平台探索OpenClaw Onboard的智能参数优化方案

最近在做一个机器人抓取相关的项目&#xff0c;遇到了参数调优的难题。传统的试错法效率太低&#xff0c;于是尝试用AI辅助开发的方式来解决这个问题。在InsCode(快马)平台上折腾了一周&#xff0c;终于搞出了一个智能参数优化方案&#xff0c;效果还不错&#xff0c;分享下我的…...

别再用Keil MDK-ARM了?手把手教你用VSCode+GCC搭建STM32F103C8T6开发环境(附标准库模板)

逃离Keil&#xff1a;用VSCodeGCC打造高效STM32开发环境 在嵌入式开发领域&#xff0c;Keil MDK-ARM长期以来都是STM32开发的主流选择。但近年来&#xff0c;越来越多的开发者开始寻求更轻量、更现代化的替代方案。如果你也对Keil的笨重界面、高昂授权费用和有限的定制能力感到…...

精选1款免费商用字体:思源宋体从选择到实战的高效应用指南

精选1款免费商用字体&#xff1a;思源宋体从选择到实战的高效应用指南 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 为什么选择免费商用字体对设计项目至关重要&#xff1f; 在当今…...

【实战 01】任务定义:从经营维度构建 Text2SQL Agent 评测基准

0. 引言&#xff1a;数据分析的“最后一公里”在大型集团的数字化实践中&#xff0c;BI 看板解决了“看数”的问题&#xff0c;但无法解决“问数”的即时性。业务人员&#xff08;如置业顾问、项目总、财务经理&#xff09;往往有大量碎片的、非标的数据需求。Text2SQL Agent 的…...

3分钟解锁B站缓存:m4s-converter让视频播放不再受限

3分钟解锁B站缓存&#xff1a;m4s-converter让视频播放不再受限 【免费下载链接】m4s-converter 一个跨平台小工具&#xff0c;将bilibili缓存的m4s格式音视频文件合并成mp4 项目地址: https://gitcode.com/gh_mirrors/m4/m4s-converter 你是否遇到过这样的情况&#xf…...