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

【LeetCode热题100】--98.验证二叉搜索树

98.验证二叉搜索树

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

image-20231003092513470

由于二叉搜索树的性质:

如果该二叉树的左子树不为空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;它的左右子树也为二叉搜索树。

这启示我们设计一个递归函数 helper(root, lower, upper) 来递归判断,函数表示考虑以 root 为根的子树,判断子树中所有节点的值是否都在 (l,r)的范围内(注意是开区间)。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回,否则我们要继续递归调用检查它的左右子树是否满足,如果都满足才说明这是一棵二叉搜索树。

那么根据二叉搜索树的性质,在递归调用左子树时,我们需要把上界 upper 改为 root.val,即调用 helper(root.left, lower, root.val),因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时,我们需要把下界 lower 改为 root.val,即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf), inf 表示一个无穷大的值。

/*** Definition for a binary tree node.* public 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;*     }* }*/
class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);}public boolean isValidBST(TreeNode node,long l,long r){if(node == null){return true;}if(node.val <= l || node.val >= r){return false;}return isValidBST(node.left,l,node.val) && isValidBST(node.right,node.val,r);}
}

相关文章:

【LeetCode热题100】--98.验证二叉搜索树

98.验证二叉搜索树 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 由于二…...

wxpython:wx.grid 表格显示 Excel xlsx文件

pip install xlrd xlrd-1.2.0-py2.py3-none-any.whl (103 kB) 摘要: Library for developers to extract data from Microsoft Excel (tm) spreadsheet files pip install wxpython4.2 wxPython-4.2.0-cp37-cp37m-win_amd64.whl (18.0 MB) Successfully installed wxpython-4.…...

事件循环机制

eventLoop 事件循环&#xff08;Event Loop&#xff09;是用于管理和调度异步任务执行的一种机制&#xff0c;通常在浏览器中&#xff0c;也在其他 JavaScript 运行环境中存在。事件循环确保 JavaScript 单线程的执行模型下能够处理非阻塞的异步任务&#xff0c;以避免程序阻塞…...

苹果曾考虑基于定位控制AirPods Pro自适应音频

在一次最近的采访中&#xff0c;苹果公司的高管Ron Huang和Eric Treski透露&#xff0c;他们在开发AirPods Pro自适应音频功能时&#xff0c;曾考虑使用GPS信号来控制音频级别。这个有趣的细节打破了我们对AirPods Pro的固有认知&#xff0c;让我们对苹果的创新思维有了更深的…...

【代码阅读笔记】yolov5 rknn模型部署

一、main函数思路 二、值得学习的地方 1、关注yolov5检测流程 2、其中几个重要的结构体 typedef struct {int left;int right;int top;int bottom; } YOLOV5_BOX_RECT; // box坐标信息typedef struct {char name[YOLOV5_NAME_MAX_SIZE];int class_index;YOLOV5_BOX_RECT box…...

【多线程】进程与线程 并发编程 面试题总结

进程和线程 进程是程序执行时的一个实例&#xff0c;即它是程序已经执行到何种程度的数据结构的汇集。从内核的观点看&#xff0c;进程的目的就是担当分配系统资源&#xff08;CPU时间、内存等&#xff09;的基本单位。线程是进程的一个执行流&#xff0c;是CPU调度和分派的基…...

C++算法 —— 动态规划(10)二维费用背包

文章目录 1、动规思路简介2、一和零3、盈利计划 背包问题需要读者先明白动态规划是什么&#xff0c;理解动规的思路&#xff0c;并不能给刚接触动规的人学习。所以最好是看了之前的动规博客&#xff0c;以及两个背包博客&#xff0c;或者你本人就已经懂得动规了。 1、动规思路简…...

MySQL数据库正在耗用大量CPU的问题排查

这是一篇实战性的文章&#xff0c;如何处理正在发生的MYSQL服务器CPU飙升的问题&#xff0c;一般情况下&#xff0c;MySQL是不会耗用这么高的CPU的&#xff0c;要么是不走索引的查询&#xff0c;要么是同一时间出现了大量比较耗用资源的查询&#xff0c;不管出现的是哪一种情况…...

php替换字符串里的a变为b

$tempstrstr_replace("\\","/",$tempstr); //把$tempstr中的a替换成b $tempstrstr_replace("a","b",$tempstr);...

黑豹程序员-架构师学习路线图-百科:CSS-网页三剑客

文章目录 1、为什么需要CSS2、发展历史3、什么是CSS4、什么是SASS、SCSS 1、为什么需要CSS 作为网页三剑客的第二&#xff0c;CSS为何需要它&#xff0c;非常简单HTML只能完成页面的展现&#xff0c;但其做出来的页面奇丑无比。 随着网络的普及&#xff0c;人们的要求更高&…...

NUWA论文阅读

论文链接&#xff1a;NUWA: Visual Synthesis Pre-training for Neural visUal World creAtion 文章目录 摘要引言相关工作视觉自回归模型视觉稀疏自注意 方法3D数据表征3D Nearby Self-Attention3D编码器-解码器训练目标 实验实现细节与SOTA比较T2I微调T2V微调V2V微调Sketch-t…...

4.Tensors For Beginners-Vector Definition

在上一节&#xff0c;已经了解了前向和后向转换。 什么是向量&#xff1f; 定义1&#xff1a;向量是一个数字列表 这很简洁&#xff0c;也通俗易懂。 现有两个向量&#xff1a; 如果要把这两个向量给加起来&#xff0c;只需把对应位置的元素(组件)给加起来。 而要缩放向量&…...

vertx学习总结5

这章我们讲回调&#xff0c;英文名&#xff1a;Beyond callbacks 一、章节覆盖&#xff1a; 回调函数及其限制&#xff0c;如网关/边缘服务示例所示 未来和承诺——链接异步操作的简单模型 响应式扩展——一个更强大的模型&#xff0c;特别适合组合异步事件流 Kotlin协程——…...

Go,从命名开始!Go的关键字和标识符全列表手册和代码示例!

目录 一、Go的关键字列表和分类介绍关键字在Go中的定位语言的基石简洁与高效可扩展性和灵活性 关键字分类声明各种代码元素组合类型的字面表示基本流程控制语法协程和延迟函数调用 二、Go的关键字全代码示例关键字全代码示例 三、Go的标识符定义基础定义特殊规定关键字与标识符…...

【网络】网络扫盲篇 ——用简单语言和图解带你入门网络

网络的一些名词和基础知识讲解 前言正式开始一些基础知识发展背景运营商和生产商 协议协议的分层TCP/IP五层(或四层)模型&#xff08;可以不看&#xff0c;对新手来说太痛苦了&#xff0c;我这里只是为了让屏幕前的你过一遍就好&#xff0c;里面很多概念新手是不太懂的&#xf…...

【项目开发 | C语言项目 | C语言薪资管理系统】

本项目是一个简单的薪资管理系统&#xff0c;旨在为用户提供方便的员工薪资管理功能&#xff0c;如添加、查询、修改、删除员工薪资信息等。系统通过命令行交互界面与用户进行交互&#xff0c;并使用 txt 文件存储员工数据。 一&#xff0c;开发环境需求 操作系统&#xff1a;w…...

Android---GC回收机制与分代回收策略

目录 GC 回收机制 垃圾回收(Garbage Collection, GC) 垃圾回收算法 JVM 分代回收策略 1. 新生代 2. 老年代 GC Log 分析 引用 GC 回收机制 垃圾回收(Garbage Collection, GC) 垃圾就是内存中已经没有用的对象&#xff0c;JVM 中的垃圾回收器(Garbage Collector)会自…...

前缀、中缀、后缀表达式相互转换工具

目录 1. 界面一览 2. 使用说明 3. 实例演示 3.1 输入中缀 3.2 输入前缀 3.3 输入后缀 3.4 选择错误的类型 4. 代码 5. 资源地址 关于什么是前缀、中缀、后缀表达式&#xff0c;相信你不知道这个东西&#xff0c;那你也不会点进来这篇博客&#xff0c;当然&#xff0c;…...

Vue之ElementUI之动态树+数据表格+分页(项目功能)

目录 前言 一、实现动态树形菜单 1. 配置相应路径 2. 创建组件 3. 配置组件与路由的关系 index.js 4. 编写动态树形菜单 5. 页面效果演示 二、实现数据表格绑定及分页功能 1. 配置相应路径 2. 编写数据表格显示及分页功能代码 BookList.vue 3. 演示效果 总结 前言…...

【CAD二次开发】给CAD添加TRUSTEDPATHS避免dll插件信任弹窗

找到配置文件目录,遍历下面的每个配置文件; 找到 Variables 下的TRUSTEDPATHS项目;在后面添加新的目录即可,多个目录使用分号分隔; public static void AddPath(string trusedPath){// 指定注册表键的路径...

利用ADS实现多频段阻抗自动优化的实战指南

1. 从零开始理解多频段阻抗匹配 刚入行那会儿&#xff0c;我对阻抗匹配的理解还停留在"把50欧姆搞对就行"的层面。直到某次调试一个同时工作在900MHz和2.4GHz的双频天线时&#xff0c;才发现单频段匹配的思路完全不够用——调好了低频段&#xff0c;高频段性能就崩了…...

RTX4090D显存优化:OpenClaw长文本处理实测Qwen3-32B性能

RTX4090D显存优化&#xff1a;OpenClaw长文本处理实测Qwen3-32B性能 1. 测试背景与实验设计 去年我在处理学术论文时&#xff0c;经常遇到需要分析几十页PDF的情况。传统工具要么截断文本&#xff0c;要么丢失关键上下文。当我发现OpenClaw支持本地部署大模型后&#xff0c;立…...

【agent原理】OpenClaw之agent全链路详解

未来已来,只需一句指令,养龙虾专栏导航,持续更新ing… openclaw的术语约定 专业术语 类比 核心作用 不用的后果 Agent Bootstrapping AI员工的入职仪式 给AI办工牌、定岗位职责、录用户信息、建工作文件夹,只执行一次 手动建文件格式错乱、agent读不到规则、配置不统一、重…...

Python中的生成器和迭代器:原理与实践

Python中的生成器和迭代器&#xff1a;原理与实践 一、背景与动机 在Python编程中&#xff0c;处理大量数据时&#xff0c;内存管理是一个常见的挑战。生成器&#xff08;Generators&#xff09;和迭代器&#xff08;Iterators&#xff09;为解决这一问题提供了一种高效的方式&…...

OpenClaw+Qwen3-VL:30B:个人多模态AI助手全流程

OpenClawQwen3-VL:30B&#xff1a;个人多模态AI助手全流程 1. 为什么选择这个组合&#xff1f; 去年冬天&#xff0c;我发现自己陷入了一个典型的知识工作者困境&#xff1a;每天要处理大量图片资料&#xff08;产品截图、会议白板照片、技术文档截图&#xff09;&#xff0c…...

IDEA插件开发实战:手把手教你开发首个效率工具(附GitHub源码)

IDEA插件开发实战&#xff1a;从零打造你的专属效率工具 JetBrains系列IDE的强大之处不仅在于其核心功能&#xff0c;更在于其开放的插件生态系统。作为一名Java开发者&#xff0c;你是否曾想过为IDEA添加一个能提升自己工作效率的专属工具&#xff1f;本文将带你从零开始&…...

SVPWM/AZSPWM的simulink仿真 AZSPWM(Advanced Zero Se...

SVPWM/AZSPWM的simulink仿真 AZSPWM&#xff08;Advanced Zero Sequence Pulse Width Modulation&#xff0c;先进零序脉宽调制&#xff09;是一种改进的脉宽调制技术&#xff0c;主要应用于三相逆变器中&#xff0c;通过引入零序分量来优化输出电压的波形和性能。 AZSPWM的目标…...

STM32姿态报警器设计:MPU6050与卡尔曼滤波实战

基于STM32的姿态翻转报警器设计与实现1. 项目概述1.1 系统架构本姿态翻转报警系统采用模块化设计&#xff0c;核心架构由STM32F103RCT6微控制器作为主控单元&#xff0c;通过I2C接口连接MPU6050惯性测量单元(IMU)传感器&#xff0c;实时采集设备的三轴加速度和三轴角速度数据。…...

颠覆PDF转换体验:Marker无缝实现25页/秒全场景文档格式精准迁移

颠覆PDF转换体验&#xff1a;Marker无缝实现25页/秒全场景文档格式精准迁移 【免费下载链接】marker 一个高效、准确的工具&#xff0c;能够将 PDF 和图像快速转换为 Markdown、JSON 和 HTML 格式&#xff0c;支持多语言和复杂布局处理&#xff0c;可选集成 LLM 提升精度&#…...

Llama-3.2V-11B-cot从零部署:Docker镜像运行与端口映射详解

Llama-3.2V-11B-cot从零部署&#xff1a;Docker镜像运行与端口映射详解 1. 项目概述 Llama-3.2V-11B-cot是基于Meta Llama-3.2V-11B-cot多模态大模型开发的高性能视觉推理工具。它针对双卡4090环境进行了深度优化&#xff0c;特别适合想要体验Llama多模态大模型但缺乏专业部署…...