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

98.验证二叉搜索树

98.验证二叉搜索树

思路

1.一开始使用递归,想当前节点满足条件后,再使左右子树分别满足条件。失败,只考虑了节点与左右子树的大小,未考虑隔代节点的关系。

2.转变思路,使用中序遍历的方法,从第一个节点开始,若出现当前节点小于前一个节点值,则不满足。测试用例出现一个较大的值。

看题解,题解也是这两种解法,递归解法额外添加了两个指针用于限定值得范围,递归左子树变上限为父节点的值,下限不变;右子树下限为父节点的值,上限不变。这样就解决了深层的子树值无法与上层节点比较的缺陷。如(5,3,7,1,6)。

中序遍历,额外申请了一个Long整数,用于保存当前前一个节点值,在遍历同时进行题目条件判断,若满足则记录当前值,继续遍历,不满足返回false退出。

代码

递归解法

class Solution {private long MIN =Long.MIN_VALUE,MAX=Long.MAX_VALUE;public boolean isValidBST(TreeNode root) {return isValid(root,MIN,MAX);}public boolean isValid(TreeNode root,Long min,Long max){if (root==null) return true;if (root.val<=min || root.val>=max) return false;return isValid(root.left,min, (long) root.val) && isValid(root.right, (long) root.val,max);}}

中序遍历解法

class Solution {private long pre =Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root==null) return true;if (!isValidBST(root.left) || root.val<=pre)return false;pre=root.val;return isValidBST(root.right);}
}

相关文章:

98.验证二叉搜索树

98.验证二叉搜索树 思路 1.一开始使用递归&#xff0c;想当前节点满足条件后&#xff0c;再使左右子树分别满足条件。失败&#xff0c;只考虑了节点与左右子树的大小&#xff0c;未考虑隔代节点的关系。 2.转变思路&#xff0c;使用中序遍历的方法&#xff0c;从第一个节点开…...

2月21日,每日信息差

&#x1f396; 素材来源官方媒体/网络新闻 &#x1f384; 10 家央企签订倡议书&#xff1a;将主动向社会开放人工智能应用场景 &#x1f30d; 上海成为首个固定资产投资破万亿的一线城市 &#x1f30b; 特斯拉扩建德国工厂的计划遭当地居民反对 &#x1f381; 加拿大公司利用木…...

android.text.BoringLayout.isBoring 的 NullPointerException

都是重写TextView.settext()函数导致的坑~ override fun setText(text: CharSequence?, type: BufferType?) {if (text.isNullOrEmpty()) {return}//业务代码super.setText(text, type)} java.lang.NullPointerException at android.text.BoringLayout.isBoring(BoringLayo…...

C++ 高频考点

1. C/C内存有哪几种类型&#xff1f; C中&#xff0c;内存分为5个区&#xff1a;堆(malloc)、栈(如局部变量、函数参数)、程序代码区&#xff08;存放二进制代码&#xff09;、全局/静态存储区&#xff08;全局变量、static变量&#xff09;和常量存储区&#xff08;常量&…...

Ubuntu安装SVN服务并结合内网穿透实现公网访问本地存储文件

最近&#xff0c;我发现了一个超级强大的人工智能学习网站。它以通俗易懂的方式呈现复杂的概念&#xff0c;而且内容风趣幽默。我觉得它对大家可能会有所帮助&#xff0c;所以我在此分享。点击这里跳转到网站。 文章目录 前言1. Ubuntu安装SVN服务2. 修改配置文件2.1 修改svns…...

2月20日,每日信息差

第一、中国联通 1 月智慧客服客户问题解决率为 97.9%&#xff0c;大联接用户达 10.02 亿户&#xff0c;5G 套餐用户约 2.64 亿户&#xff0c;物联网终端连接约 5.06 亿户。5G 行业虚拟专网服务客户数为 9185 个&#xff0c;智慧客服问题解决率 97.9%&#xff0c;智能服务占比 8…...

Visual Studio清单作用

1、作用&#xff1a; 制定程序依赖的C运行库的dll及版本&#xff0c;包括mfc&#xff0c;atl&#xff0c;crt等&#xff0c;在Visual Studio安装目录下的vc/redist下有debug和release版本 2、确定应用程序依赖哪些visual C 库方法&#xff1a; 查看项目-》项目设置-》常规&…...

Java中的==和equals()方法的区别是?hashCode()和equals()的关系是什么?

目录 解释Java中的和equals()方法。 hashCode()和equals()的关系是什么&#xff1f; 解释Java中的和equals()方法。 在Java中&#xff0c;和equals()方法都用于比较两个对象&#xff0c;但它们在比较时的侧重点和行为上有所不同。 1. **运算符&#xff1a;** - 是Java中的…...

yaml-cpp开源库使用

源码下载&#xff1a;https://github.com/jbeder/yaml-cpp 1.yaml-cpp编译 步骤主要如下&#xff1a;进入源码目录后 mkdir build cd build cmake … make make install 2.代码示例 #include "funset.hpp" #include <string> #include <fstream> #i…...

【C++私房菜】序列式容器的迭代器失效问题

目录 一、list的迭代器失效 二、vector的迭代器失效 1、空间缩小操作 2、空间扩大操作 三、总结 在C中&#xff0c;当对容器进行插入或删除操作时&#xff0c;可能会导致迭代器失效的问题。所谓迭代器失效指的是&#xff0c;原先指向容器中某个元素的迭代器&#xff0c;在…...

MySQL 篇-深入了解 DML、DQL 语言(二)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 DML、DQL 语言说明 2.0 使用 DML 实现对数据管理和操作 2.1 DML - 增添数据 insert 2.2 DML - 修改数据 update 2.3 DML - 删除数据 delete 3.0 使用 DQL 实现对…...

端智能:面向手机计算环境的端云协同AI技术创新

近年来&#xff0c;随着移动端设备软硬件能力的进步&#xff0c;移动端的算力有了很大提升&#xff0c;同时面向移动端的机器学习框架和模型轻量化技术越来越成熟&#xff0c;端上的AI能力逐渐进入大众视野&#xff0c;端智能在电商领域也开始逐步走向规模化应用。通过持续探索…...

PHP函数 “password_hash“ 哈希密码

哈希函数是一种将输入转换为固定长度字符串的方法&#xff0c;这个过程是不可逆的&#xff0c;也就是无法从哈希值还原出原始输入。通过将密码进行哈希处理&#xff0c;即使数据库泄露&#xff0c;攻击者也无法简单地获取到用户密码。 在PHP中&#xff0c;我们可以使用 "…...

第十一天-Excel的操作

目录 1.xlrd-Excel的读模块 安装 使用 获取工作簿 读取工作簿的内容 xlsxwriter-Excel的写模块 安装 使用 生成图表 add_series参数 图表的样式 demo&#xff1a;生成图表 Excel的操作在python中有多个模块&#xff0c;为了能够快速使用&#xff0c;选择了相对简单…...

【java任意文件漏洞修复,使用文件魔数解决】

java任意文件漏洞修复&#xff0c;使用文件魔数解决 背景&#xff1a; 客户进行渗透测试&#xff0c;验证上传文件的程序没有对上传文件作任何过滤&#xff0c;导致可以上传任意文件到服务器&#xff0c;甚至是病毒文件和Webshell木马文件。 解决办法&#xff1a;对于上传的附件…...

LeetCode 热题 100 | 二叉树(二)

目录 1 543. 二叉树的直径 2 102. 二叉树的层序遍历 3 108. 将有序数组转换为二叉搜索树 菜鸟做题&#xff0c;语言是 C 1 543. 二叉树的直径 这道题和 124. 二叉树中的最大路径和 太像了 题眼&#xff1a;二叉树的 直径 是指树中任意两个节点之间 最长路径的长度 。…...

mini-spring|定义标记类型Aware接口,实现感知容器对象

**前言&#xff1a;**如果我们想获得 Spring 框架提供的 BeanFactory、ApplicationContext、BeanClassLoader等这些能力做一些扩展框架的使用时该怎么操作呢。所以我们本章节希望在 Spring 框架中提供一种能感知容器操作的接口&#xff0c;如果谁实现了这样的一个接口&#xff…...

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 输入:head = [1,1,2] 输出:[1,2] 输入:head = [1,1,2,3,3] 输出:[1,2,3] 提示: 链表中节点数目在范围 [0, 300] 内-100 <= Node.val <= 100题目数据保证链表已…...

贪心算法

贪心算法 例题1、股票买卖题目信息思路题解 2、货仓选址题目信息思路题解 3、糖果传递题目信息思路题解 4、雷达设备题目信息思路题解 例题 1、股票买卖 题目信息 思路 相邻两天&#xff0c;后>前&#xff0c;则交易一次 题解 #include <bits/stdc.h> #define en…...

MySQL基本知识

目录 一&#xff0c;MySQL的元数据库 1.1.什么是元数据库 1.2.有哪些元数据库 1.3.切换数据库 二&#xff0c;账户管理 2.1.设置权限 2.2.授权用户 2.3.查看权限 2.4.撤销权限 三&#xff0c;MySQL引擎 3.1什么是数据库引擎 3.2.查看数据引擎 3.3.MyISAM引擎 3.4…...

【AGI物流落地倒计时】:为什么2026年Q2成为企业接入自主决策物流AI的最后窗口期?

第一章&#xff1a;2026奇点智能技术大会&#xff1a;AGI与物流管理 2026奇点智能技术大会(https://ml-summit.org) AGI驱动的动态物流决策中枢 在2026奇点智能技术大会上&#xff0c;多家头部物流企业联合发布了基于自主推理架构&#xff08;Autonomous Reasoning Architect…...

CSS如何消除图片下方多余间隙_设置display-block改变盒模型

图片下方空白源于img默认inline导致的基线对齐&#xff1b;display:block最直接有效&#xff0c;vertical-align:middle等有兼容性与场景限制&#xff0c;font-size:0或line-height:0副作用大。图片下方空白是行内元素的基线对齐导致的默认情况下 <img> 是行内元素&#…...

四十二、Fluent欧拉模型流化床模拟:从基础设置到颗粒动力学解析

1. 流化床与欧拉模型基础概念 流化床技术在现代工业中应用广泛&#xff0c;从化工反应器到生物质燃烧装置都能见到它的身影。简单来说&#xff0c;流化床就是让固体颗粒在流体作用下呈现类似流体流动状态的一种装置。想象一下小时候玩过的泡泡浴&#xff0c;当浴缸底部不断有气…...

告别工厂模式:用更清晰的方式在Spring Boot里玩转MQTT发布与订阅(附可运行Demo)

Spring Boot极简MQTT实战&#xff1a;从零构建智能灯控系统 物联网开发中&#xff0c;MQTT协议因其轻量级和高效性成为设备通信的首选方案。但对于刚接触Spring Boot的开发者来说&#xff0c;网上充斥着大量使用复杂工厂模式的实现方案&#xff0c;不仅增加了学习曲线&#xff…...

告别原生局限:手把手教你为QML应用注入KDDockWidgets窗口停靠能力(Windows/Mac双平台配置指南)

突破QML窗口管理瓶颈&#xff1a;KDDockWidgets跨平台整合实战 在构建现代化桌面应用时&#xff0c;窗口停靠系统是提升用户体验的关键组件。然而Qt框架长期存在一个明显的功能缺口——官方QML模块缺乏原生的DockWidget支持。这种局限性迫使开发者要么接受功能残缺&#xff0c;…...

springboot中医“知源”小程序(文档+源码)_kaic

系统实现用户前台功能&#xff08;前端&#xff09;用户注册模块用户在填写数据的时候必须与注册页面上的验证相匹配否则会注册失败&#xff0c;注册页面的表单验证是通过JavaScript进行验证的&#xff0c;用户名的长度必须在6到18之间&#xff0c;邮箱必须带有符号&#xff0c…...

家里装修别乱接!电工师傅教你一眼分清零线火线,安全又省钱

家庭电路安全指南&#xff1a;零线火线快速识别与正确接线技巧 装修新房或改造旧电路时&#xff0c;最让人头疼的莫过于面对一堆颜色各异的电线不知如何下手。不少朋友抱着"反正都是电&#xff0c;接上能亮就行"的心态随意接线&#xff0c;轻则导致电器损坏&#xff…...

超星学习通/中科大实验室安全考试自动答题脚本保姆级教程(Python版,含Cookie获取)

超星学习通实验室安全考试自动化解决方案实战指南 实验室安全考试是高校学生必须面对的常规考核之一&#xff0c;但反复刷题的过程往往耗时费力。作为一名长期研究教育自动化工具的技术爱好者&#xff0c;我发现通过Python脚本与浏览器开发者工具的结合&#xff0c;可以高效解决…...

【技术底稿 18】FTP 文件处理 + LibreOffice Word 转 PDF 在线预览 + 集群乱码终极排查全记录

一、前言 本文为生产环境实战复盘技术底稿&#xff0c;聚焦后端通用文件处理场景&#xff0c;完整实现基于 LibreOffice 的 Word 转 PDF 在线预览接口。全文完整复盘 FTP 底层连接污染问题、分布式集群交替乱码玄学问题&#xff0c;沉淀可复用的生产开发规范与运维经验&#x…...

JavaScript的Promise.withResolvers:分离Promise的创建与解决

JavaScript的Promise.withResolvers&#xff1a;分离Promise的创建与解决 在JavaScript的异步编程中&#xff0c;Promise是处理异步操作的核心工具之一。传统的Promise构造函数将创建与解决逻辑耦合在一起&#xff0c;而ES2024引入的Promise.withResolvers方法则提供了一种更灵…...