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

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...