当前位置: 首页 > 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){// 指定注册表键的路径...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...