记录算法笔记(2025.5.17)验证二叉搜索树
给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。提示:
- 树中节点数目范围在
[1, 104]
内 -231 <= Node.val <= 231 - 1
思路:
初始化
-
创建一个栈,用于存储尚未处理的节点。
-
设置一个变量
lastTreeNode
,用于记录上一个访问的节点的值。初始值为long.MinValue
,确保第一个节点的值总是大于它。 -
设置一个指针
current
,初始指向根节点root
。
主循环
循环条件是:current
不为 null
或者栈不为空。这意味着还有节点需要处理。
-
将所有左子节点压入栈:
-
从当前节点
current
开始,沿着左子树一直向下,将所有左子节点依次压入栈中。 -
每次将当前节点压入栈后,将
current
指向它的左子节点。 -
这一步确保了左子树的所有节点都被处理。
-
-
弹出栈顶节点并访问:
-
当左子树的所有节点都被压入栈后,弹出栈顶节点。此时,栈顶节点是当前需要访问的节点。
-
将弹出的节点赋值给
current
。
-
-
检查当前节点值是否满足BST性质:
-
比较当前节点的值
current.val
和上一个访问的节点值lastTreeNode
。 -
如果当前节点的值小于或等于
lastTreeNode
,说明这棵树不是有效的BST,直接返回false
。
-
-
更新上一个访问的节点值:
-
将当前节点的值赋值给
lastTreeNode
,以便在下一次循环中使用。
-
-
转向右子树:
-
将
current
指向当前节点的右子节点。 -
如果当前节点没有右子节点,
current
会变成null
,循环会继续从栈中弹出下一个节点(即当前节点的祖先节点的右子树)。
-
循环结束
-
当
current
为null
且栈为空时,说明所有节点都已处理完毕。 -
如果在整个遍历过程中没有发现任何违反BST性质的情况,返回
true
,表示这棵树是有效的BST。
代码:C#
public class Solution {
public bool IsValidBST(TreeNode root) {
if(root==null)
return true;
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode current=root;
long lastTreeNode=long.MinValue;
while(current!=null ||stack.Count>0)
{
//将所有左子节点存入这个栈中,而且最低下是根节点
while(current!=null)
{
stack.Push(current);
current=current.left;
}
//弹出栈的一个节点
current=stack.Pop();
//判断当前节点是否小于上一个节点,第一次进入的时候是跟最小值比,第一个节点值随便多大
if(current.val<=lastTreeNode)
{
return false;
}
//记下当前节点的值
lastTreeNode=current.val;
//将当前节点转为右子树届节点
current=current.right;
}
return true;
}
}
相关文章:
记录算法笔记(2025.5.17)验证二叉搜索树
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 1: 输入&…...
DataX:一个开源的离线数据同步工具
DataX 是一个异构数据源离线同步(ETL)工具,实现了包括关系型数据库(MySQL、Oracle 等)、HDFS、Hive、ODPS、HBase、FTP 等各种异构数据源之间稳定高效的数据同步功能。它也是阿里云 DataWorks 数据集成功能的开源版本。 为了解决异构数据源同…...
剑指offer第一周
目录 二维数组中的查找 旋转数组的最小数字 调整数组顺序使奇数位于偶数前面 数组中出现次数超过一半的数字 替换空格 从尾到头打印链表 重建二叉树 矩形覆盖 链表中倒数最后k个结点 二进制中1的个数 合并两个排序的链表 树的子结构 二叉树的镜像 二…...
素数筛(欧拉筛算法)
#include<bits/stdc.h> using namespace std; #define maxn 100000 int vis[maxn]; int prime[maxn]; //欧拉筛函数 int Euler_sieve(int n) { int i,j,k; k0;//保存素数的个数 memset(vis,0,sizeof(int)*maxn);//初始化数组 for(i2;i<n;i) { if(vis[i]0)//i是素数…...
遨游科普:三防平板是什么?有什么功能?
清晨的露珠还挂在帐篷边缘,背包里的三防平板却已开机导航;工地的尘土飞扬中,工程师正通过它查看施工图纸;暴雨倾盆的救援现场,应急队员用它实时回传灾情数据……这些看似科幻的场景,正因三防平板的普及成为…...
CSS 浮动与定位以及定位中z-index的堆叠问题
CSS 浮动与定位以及定位中z-index的堆叠问题 一、浮动布局的特点与应用 1. 浮动核心特性 脱离标准流:浮动元素会脱离文档流。环绕特性:后续内容会环绕浮动元素排列自动换行:多个浮动元素在容器宽度不足时自动换行 .float-box {float: lef…...
在Maven中替换文件内容的插件和方法
在Maven中替换文件内容的插件和方法 Maven提供了几种方式来替换文件内容,以下是常用的插件和方法: 1. maven-replacer-plugin (推荐) 这是专门用于文件内容替换的插件,功能强大且灵活。 基本配置 <plugin><groupId>com.goog…...
C# lock
在C#中,lock关键字用于确保当一个线程位于给定实例的代码块中时,其他线程无法访问同一实例的该代码块。这是一种简单的同步机制,用来防止多个线程同时访问共享资源或执行需要独占访问的代码段(临界区),从而…...
OGGMA 21c 微服务 (MySQL) 安装避坑指南
前言 这两天在写 100 天实战课程 的 OGG 微服务课程: 在 Oracle Linux 8.10 上安装 OGGMA 21c MySQL 遇到了一点问题,分享给大家一起避坑! 环境信息 环境信息: 主机版本主机名实例名MySQL 版本IP 地址数据库字符集Goldengate …...
NPN、PNP三极管的应用
由于电路知识实在是难以拿出手,在面试的时候被问到三极管相关问题,相当地尴尬。在网上简要地学习了相关的理论知识,在这里给出自己的理解。更为基础的原理在这里并不提及。我们面向实际应用学习即可。 我们知道常见的三极管总是硅管ÿ…...
Cadence Allegro安装教程及指导
Cadence Allegro 是一款专业的 PCB 设计软件,被广泛应用于电子行业。它功能强大,能够处理复杂的电路板设计任务。下面为你详细介绍 Cadence Allegro 的安装步骤。 一、安装前准备 在安装 Cadence Allegro 之前,需要进行一系列准备工作&…...
阿里通义万相 Wan2.1-VACE:开启视频创作新境界
2025 年 5 月 14 日,阿里巴巴为视频创作领域带来了重磅惊喜 —— 开源通义万相 Wan2.1-VACE。这一模型堪称视频生成与编辑领域的集大成者,凭借其全面且强大的功能,为广大创作者、开发者以及企业用户开辟了全新的视频创作天地。它打破了以往视…...
mAP、AP50、AR50:目标检测中的核心评价指标解析
在目标检测任务中,评价指标是衡量模型性能的核心工具。其中,mAP(mean Average Precision)、AP50(Average Precision at IoU0.5)和AR50(Average Recall at IoU0.5)是最常用的指标。本…...
Linux进程异常退出排查指南
在 Linux 中,如果进程无法正常终止(如 kill 命令无效)或异常退出,可以按照以下步骤排查和解决: 1. 常规终止进程 尝试普通终止(SIGTERM) kill PID # 发送 SIGTERM 信号(…...
深入解析:如何基于开源OpENer开发EtherNet/IP从站服务
一、EtherNet/IP协议概述 EtherNet/IP(Industrial Protocol)是一种基于以太网的工业自动化通信协议,它将CIP(Common Industrial Protocol)封装在标准以太网帧中,通过TCP/IP和UDP/IP实现工业设备间的通信。作为ODVA(Open DeviceNet Vendors Association)组织的核心协议…...
【Linux 学习计划】-- yum
目录 什么是yum Linux的生态讲解 yum相关操作 yum源 yum配置相关问题 结语 什么是yum 我们的手机上都有手机自带的软件商城,我们下载软件都可以在上面搜索,安装,下载 而我们的yum就是这么一个东西,他其实就是Linux下的安装…...
Qt 强大的窗口停靠浮动
1、左边: 示例代码: CDockManager::setConfigFlags(CDockManager::DefaultOpaqueConfig); CDockManager::setConfigFlag(CDockManager::FocusHighlighting, true); dockManager new CDockManager(this); // Disabling the Internal Style S…...
Flink 数据传输机制
在 Apache Flink 中,数据传输(Data Transmission)机制 是其分布式流处理能力的核心之一。Flink 通过高效的内部数据交换、网络通信和序列化机制,确保任务之间的数据能够高效、可靠地流动。 一、Flink 数据传输的基本流程 Source …...
数据库——SQL约束窗口函数介绍
4.SQL约束介绍 (1)主键约束 A、基本内容 基本内容 p r i m a r y primary primary k e y key key约束唯一表示数据库中的每条记录主键必须包含唯一的值(UNIQUE)主键不能包含NULL值(NOT NULL)每个表都应…...
第8讲、Multi-Head Attention 的核心机制与实现细节
🤔 为什么要有 Multi-Head Attention? 单个 Attention 机制虽然可以捕捉句子中不同词之间的关系,但它只能关注一种角度或模式。 Multi-Head 的作用是: 多个头 多个视角同时观察序列的不同关系。 例如: 一个头可能专…...
【发票提取表格】批量PDF电子发票提取明细保存到Excel表格,批量提取ODF电子发票明细,行程单明细,单据明细保存到表格,使用步骤、详细操作方法和注意事项
在日常办公中,我们常常会面临从大量 PDF 电子发票、ODF 电子发票、行程单及各类单据中提取明细,并整理到 Excel 表格的艰巨任务。手动操作不仅耗时费力,还极易出错。以下为您详细介绍其使用步骤、操作方法、注意事项及应用场景。 一、适用场…...
React中startTransition的使用
// 引入 React 的 Hook API:useState 管理状态、useTransition 处理非紧急更新、useMemo 缓存计算结果 import { useState, useTransition, useMemo } from react;/*** List 组件:* 根据输入的 query 动态渲染一个包含 10000 条数据的列表*/ function Li…...
Reactor (epoll实现基础)
Reactor 是什么? Reactor 网络模型是一种高性能的事件驱动模型,广泛应用于网络编程中。它通过 I/O 多路复用技术,实现了高效的事件处理和系统吞吐量的优化。 核心概念 Reactor 模型_的核心是事件驱动,即当 I/O 事件准备就绪时_…...
php fiber 应用
参考 基于 PHP Fiber(纤程)的游戏开发分析-腾讯云开发者社区-腾讯云PHP 8.1 引入的 Fibers 为游戏开发带来新机遇,能管理渲染、物理计算等任务且不阻塞主线程。它支持并发,提升效率,简单易用,但也有局限&a…...
前端扫盲HTML
文章目录 下载、安装、运行第一个代码(hello world)创建代码文件编辑代码(hello world)HTML常见标签注释标签标题标签段落标签换行标签格式化标签图片标签表格标签列表标签表单标签下拉菜单无语义标签 参考文档 下载、安装、运行第…...
RAG与微调:企业知识库落地的技术选型
从本质上看,RAG是"让模型查阅外部知识",而微调是"让模型学会并内化知识"。这一根本差异决定了它们在不同场景下的适用性。 技术选型的关键依据 场景RAG微调说明模型定制化需求❌✅微调更适合塑造特定风格、口吻和人格特征硬件资源…...
Linux安全篇 --firewalld
一、Firewalld 防火墙概述 1、Firewalld 简介 firewalld 的作用是为包过滤机制提供匹配规则(或称为策略),通过各种不同的规则告诉netfilter 对来自指定源、前往指定目的或具有某些协议特征的数据包采取何种处理方式为了更加方便地组织和管理防火墙,firewalld 提供…...
关于Android Studio for Platform的使用记录
文章目录 简单介绍如何使用配置导入aosp工程配置文件asfp-config.json 简单介绍 Android Studio for Platform是google最新开发,用来阅读aosp源码的工具 详细的资料介绍: https://developer.android.google.cn/studio/platform 将工具下载下来直接点击…...
搜索引擎工作原理|倒排索引|query改写|CTR点击率预估|爬虫
写在前面 使用搜索引擎是我们经常做的事情,搜索引擎的实现原理。 什么是搜索引擎 搜索引擎是一种在线搜索工具,当用户在搜索框输入关键词时,搜索引擎就会将与该关键词相关的内容展示给用户。比较大型的搜索引擎有谷歌,百度&…...
【找工作系列①】【大四毕业】【复习】巩固JavaScript,了解ES6。
文章目录 前言Tasks:复习笔记:JavaScript是什么?JavaScript有什么用或者换句话说 是做什么的?JavaScript由哪几部分组成?BOM?DOM?html文件中script标签放在哪里?🧩 1. **放在 ****<head>**** 中**✅ 优点&…...
Oracle 11.2.0.4 pre PSU Oct18 设置SSL连接
Oracle 11.2.0.4 pre PSU Oct18 设置SSL连接 1 说明2 客户端配置jdk环境3服务器检查oracle数据库补丁4设置ssla 服务器配置walletb 上传测试脚本和配置文件到客户端c 服务器修改数据库侦听和sqlnet.orad 修改客户端的sqlnet.ora和tnsnames.ora的连接符e 修改java代码的数据连接…...
本地部署开源网盘系统 kiftd 并实现外部访问(Linux 版本)
kiftd 是一款专为个人、团队及小型组织设计的开源网盘系统,兼具便捷性、跨平台兼容性与丰富的功能,成为替代传统文件共享工具的理想选择。 本文将详细介绍如何在 Linux 系统本地部署 kiftd 并结合路由侠实现外网访问本地部署的 kiftd 。 第一步&#x…...
ECS/GEM是半导体制造业的标准通信协议中host和equipment的区别是什么,在交互过程中,如何来定位角色谁为host,谁为equipment
文章目录 一、角色定义与核心区别1. Host(主机)2. Equipment(设备)3. Host与Equipment的核心区别 二、交互过程中的角色定位1. 交互方向2. 控制层级3. 交互过程中角色的定位方法3.1. 通信发起方向3.2. 协议功能与状态管理3.3. 物理…...
5000 字总结CSS 中的过渡、动画和变换详解
CSS 中的过渡、动画和变换详解 一、CSS 过渡(Transitions) 1. 基本概念 CSS 过渡是一种平滑改变 CSS 属性值的机制,允许属性值在一定时间内从一个值逐渐变化到另一个值,从而创建流畅的动画效果。过渡只能用于具有中间值的属性&…...
2025年渗透测试面试题总结-安恒[实习]安全工程师(题目+回答)
网络安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 安恒[实习]安全工程师 一面 1. 自我介绍 2. 前两段实习做了些什么 3. 中等难度的算法题 4. Java的C…...
WebXR教学 09 项目7 使用python从0搭建一个简易个人博客
WebXR教学 09 项目7 使用python从0搭建一个简易个人博客(1) 前期设计规划 功能 呈现个人博客文章 技术选型 HTMLCSSJSPythonFlask 环境准备 VS Code Python3.8 代码实现 包 # 创建虚拟环境(-m 会先将模块所在路径加入 sys.path,更适…...
c++从入门到精通(五)--异常处理,命名空间,多继承与虚继承
异常处理 栈展开过程: 栈展开过程沿着嵌套函数的调用链不断查找,直到找到了与异常匹配的catch子句为止;也可能一直没找到匹配的catch,则退出主函数后查找过程终止。栈展开过程中的对象被自动销毁。 在栈展开的过程中,…...
开源安全大模型Foundation-Sec-8B实操
一、兴奋时刻 此时此刻,晚上22点55分,从今天早上6点左右开始折腾,花费了接近10刀的环境使用费,1天的休息时间,总算是把Foundation-Sec-8B模型跑起来了,中间有两次胜利就在眼前,但却总在远程端口转发环节出问题,让人难受。直到晚上远程Jupyter访问成功那一刻,眉开眼笑,…...
现代优化算法全解析:禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、人工神经网络
现代优化算法全解析:禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、人工神经网络 引言:为什么需要优化算法? 在当今这个数据驱动的时代,优化算法已成为计算机科学、工程设计、人工智能等领域的核心工具。无论是训练神经…...
Docker常见命令解读
上图是对docker常见命令的一个图解,方便大家理解,下面,我将对这些命令做一些解释。 一、镜像生命周期管理 1. 镜像构建(Build) docker build -t my-image . # 根据Dockerfile构建镜像 Dockerfile:…...
为什么 Docker 建议关闭 Swap
在使用 Docker 时,关闭系统 Swap(交换分区) 是一个常见的推荐做法,尤其是在生产环境中。虽然 Docker 不强制要求禁用 Swap,但出于性能、稳定性、可控性和资源管理的目的,通常建议这样做。 为什么 Docker 建…...
TIFS2024 | CRFA | 基于关键区域特征攻击提升对抗样本迁移性
Improving Transferability of Adversarial Samples via Critical Region-Oriented Feature-Level Attack 摘要-Abstract引言-Introduction相关工作-Related Work提出的方法-Proposed Method问题分析-Problem Analysis扰动注意力感知加权-Perturbation Attention-Aware Weighti…...
WPS PPT设置默认文本框
被一个模板折磨了好久,每次输入文本框都是很丑的24号粗体还有行标,非常恶心,我甚至不知道如何描述自己的问题,非常憋屈,后来终于知道怎么修改文本框了。这种软件操作问题甚至不知道如何描述问题本身,非常烦…...
支持selenium的chrome driver更新到136.0.7103.94
最近chrome释放新版本:136.0.7103.94 如果运行selenium自动化测试出现以下问题,是需要升级chromedriver才可以解决的。 selenium.common.exceptions.SessionNotCreatedException: Message: session not created: This version of ChromeDriver only su…...
“下一辆车还买小米”
大家好,我是小悟。 就在5月13日,江西上饶德兴街头,一辆紫色小米SU7 Max停在路边,却遭遇了一场堪比灾难片的意外。 一辆满载货物的大货车因手刹故障溜坡,径直撞向SU7,两车从两米高的落差坠落,货…...
opencv4.11生成ArUco标记 ArUco Marker
从opencv4.7开始aruco有了一些变化 以下是opencv4.11生成ArUco标记的小例子 #include <iostream> #include <opencv2/opencv.hpp> #include <opencv2/objdetect/aruco_detector.hpp>int main() {cv::Mat markerImage;cv::aruco::Dictionary dictionary cv…...
从辅助到协作:GitHub Copilot的进化之路
如果说现代程序员的标配工具除了VS Code、Stack Overflow之外,还有谁能入选,那一定是GitHub Copilot。从2021年首次亮相,到如今深度集成进开发者日常流程,这个“AI编程助手”已经不只是写几行自动补全代码的小帮手了,而…...
QMK 宏(Macros)功能详解(实战部分)
QMK 宏(Macros)功能详解(实战部分) 一、宏的基本概念与作用 宏(Macros)是 QMK 固件中一项强大的功能,它允许您在按下单个按键时执行多个按键操作。通过宏,您可以: 输入常用短语或文本执行复杂的按键组合自动化重复性操作触发系统功能或快捷键🔔 安全提示:虽然可以…...
SVN 版本控制入门指南
SVN 版本控制系统详细入门指南 一、SVN 基础概念详解 1. 什么是版本控制? 版本控制是一种记录文件变化的系统,可以: 追踪文件的修改历史查看每次修改的内容恢复到任意历史版本协调多人协作开发 2. SVN 核心概念 2.1 仓库(Re…...
6to4、6over4的类比解释
本文由deepseek生成,特此声明 1. 6to4:自动的“快递中转站” 类比场景: 假设你住在一个偏远的小镇(IPv6网络),周围被大海(IPv4互联网)包围,你想给另一个偏远小镇&#…...