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

【LeetCode-中等题】98. 验证二叉搜索树

文章目录

    • 题目
    • 方法一:BFS 层序遍历
    • 方法二: 递归
    • 方法三: 中序遍历(栈)
    • 方法四: 中序遍历(递归)

题目

在这里插入图片描述
在这里插入图片描述

思路就是首先得知道什么是二叉搜索树
左孩子在(父节点的最小值,父节点)区间内
右孩子在(父节点,父节点的最大值)区间内
只要满足这两点就行

方法一:BFS 层序遍历

利用层序遍历 拿到每一个节点 并且给每一个结点配备一个最大值和最小值的队列
只要节点在最大值和最小值之间就满足二叉搜索树的条件
在这里插入图片描述

在这里插入图片描述

public boolean isValidBST(TreeNode root) {if(root == null) return true;Queue<TreeNode> queue = new LinkedList<>();Queue<Long> minValues = new LinkedList<>();//定义两个队列来记录每一个节点的最大值和最小值情况  Queue<Long> maxValues = new LinkedList<>();queue.offer(root);minValues.offer(Long.MIN_VALUE); // 初始最小值为maxValues.offer(Long.MAX_VALUE); // 初始最大值为while(!queue.isEmpty()){int count = queue.size();for(int i = 0 ; i < count ; i++){TreeNode node =  queue.poll();Long minValue = minValues.poll();//弹出该对比节点的最大值和最小值情况   节点值必须在这个区间内才满足条件Long maxValue = maxValues.poll();if (  node.val <= minValue ||  node.val >= maxValue) {return false;}if(node.left != null){queue.offer(node.left);minValues.offer(minValue);//  左子树的最小值沿用上一次的最小值maxValues.offer((long)node.val); // 左子树的最大值为当前节点值}if(node.right != null){queue.offer(node.right);minValues.offer((long)node.val); // 右子树的最小值为当前节点值maxValues.offer(maxValue); // 右子树的最大值沿用上一次的最大值}}}return true;}

方法二: 递归

	   // root.val要在  (min,max) 区间才是二叉搜索数//  判断左子树 和右子树是否是搜索二叉树   //   ==左孩子在(父节点的最小值,父节点)区间内==// 	  ==右孩子在(父节点,父节点的最大值)区间内==
    public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);   // 不能用Integer.MAX  2147483647  案例有root就等于2147483647  明显不满足搜索树}public boolean isValidBST(TreeNode root,long  min,long  max) {if(root == null ){return true;}if(root.val <= min || root.val >= max) return false;//root.val要在  (min,max) 区间才是二叉搜索数return isValidBST(root.left,min,root.val)&&isValidBST(root.right,root.val,max);//判断左子树 和右子树是否是搜索二叉树   //   ==左孩子在(父节点的最小值,父节点)区间内==// 	  ==右孩子在(父节点,父节点的最大值)区间内==}

方法三: 中序遍历(栈)

  1. 核心先遍历左子树,直到左子树为null 再去遍历右子树,直到右子树为null
  2. 每弹出一个节点的值小于等于前一个 inorder,说明不是二叉搜索树
  3. 在遍历右子树的同时 更新inorder值为当前节点
  public boolean isValidBST(TreeNode root) {Deque<TreeNode> stack = new LinkedList<TreeNode>();//栈Long inorder = Long.MIN_VALUE;while(!stack.isEmpty() || root !=null){while(root != null){//先去遍历左子树stack.push(root);root = root.left;}root = stack.pop();// 如果中序遍历得到的节点的值小于等于前一个 inorder,说明不是二叉搜索树if(root.val <= inorder) return false;inorder = (long)root.val;root = root.right;//遍历右子树}return true;}

方法四: 中序遍历(递归)

中序遍历时,判断当前节点是否大于中序遍历的前一个节点,如果大于,说明满足 BST,继续遍历;否则直接返回 false。

 long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) return true;//判断左子树是不是 二叉搜索时if(!isValidBST(root.left)) return false;if(root.val <= pre) return false ;else pre = root.val;//判断右子树是不是 二叉搜索时if(!isValidBST(root.right)) return false;return true;}

相关文章:

【LeetCode-中等题】98. 验证二叉搜索树

文章目录 题目方法一&#xff1a;BFS 层序遍历方法二&#xff1a; 递归方法三&#xff1a; 中序遍历&#xff08;栈&#xff09;方法四&#xff1a; 中序遍历&#xff08;递归&#xff09; 题目 思路就是首先得知道什么是二叉搜索树 左孩子在&#xff08;父节点的最小值&#x…...

Leetcode-每日一题【剑指 Offer 37. 序列化二叉树】

题目 请实现两个函数&#xff0c;分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑&#xff0c;你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 …...

删除无点击数据offer数据分析使用

梳理思路&#xff1a; 1、 获取 7month 和 8month fullreport 报表中 所有offer&#xff1b;输出结果&#xff1a;offerid&#xff0c; totalClickCount&#xff1b; 2、 分析数据7month totalClickCount0 and 8month totalClickCount0 的offer去除&#xff1b; result.…...

【Apollo学习笔记】——规划模块TASK之SPEED_BOUNDS_PRIORI_DECIDER

文章目录 前言SPEED_BOUNDS_PRIORI_DECIDER功能简介SPEED_BOUNDS_PRIORI_DECIDER相关配置SPEED_BOUNDS_PRIORI_DECIDER流程将障碍物映射到ST图中ComputeSTBoundary(PathDecision* path_decision)ComputeSTBoundary(Obstacle* obstacle)GetOverlapBoundaryPointsComputeSTBounda…...

物理机ping不通windows server 2012

刚才尝试各种方法&#xff0c;在物理机上就是ping不能wmware中的windows server 2012 . 折腾了几个小时&#xff0c;原来是icmp 被windows server 2012 禁用了 现在使用使用以下协议就能启用Icmp协议。 netsh firewall set icmpsetting 8然后&#xff0c;就能正常ping 通虚…...

誉天HCIE-Datacom丨为什么选择誉天数通HCIE课程学习

大家好&#xff0c;我是誉天HCIE-Datacom的一名学员&#xff0c;在2022年觉得自己技术水平不够&#xff0c;想要提升自己&#xff0c;经朋友介绍在誉天报的名。 听朋友说誉天的阮Sir的课讲的非常好&#xff0c;我在B站上看了几节阮老师的课确实比之前在听得其他机构的课程讲的要…...

Python文本终端GUI框架详解

今天笔者带大家&#xff0c;梳理几个常见的基于文本终端的 UI 框架&#xff0c;一睹为快&#xff01; Curses 首先出场的是 Curses。 Curses 是一个能提供基于文本终端窗口功能的动态库&#xff0c;它可以: 使用整个屏幕 创建和管理一个窗口 使用 8 种不同的彩色 为程序提供…...

01_lwip_raw_udp_test

1.打开UDP的调试功能 &#xff08;1&#xff09;设置宏定义 &#xff08;2&#xff09;打开UDP的调试功能 &#xff08;3&#xff09;修改内容&#xff0c;串口助手打印的日志信息自动换行 2.电脑端连接 UDP发送一帧数据 3.电路板上发送一帧数据...

学习ts(十一)本地存储与发布订阅模式

localStorage实现过期时间 目录 准备 安装 npm i rollup typescript rollup-plugin-typescript2// tsconfig.json"module": "ESNext","moduleResolution": "node", "strict": false, // rollup.config.js import …...

MySQL对NULL值处理

在使用数据库时&#xff0c;有时需要表示未知值&#xff0c;这时可以使用NULL值表示。引入NULL值后&#xff0c;会对原有的使用产生影响&#xff0c;这里记录下常见的场景&#xff0c;以做记录。 NULL含义 在MySQL中&#xff0c;NULL值表示一个未知值&#xff0c;表示不可知、…...

Vector 动态数组(迭代器)

C数据结构与算法 目录 本文前驱课程 1 C自学精简教程 目录(必读) 2 Vector<T> 动态数组&#xff08;模板语法&#xff09; 本文目标 1 熟悉迭代器设计模式&#xff1b; 2 实现数组的迭代器&#xff1b; 3 基于迭代器的容器遍历&#xff1b; 迭代器语法介绍 对迭…...

多组背包恰好装满方案数

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 现在有一个大小n*1的收纳盒&#xff0c;我们手里有无数个大小为1*1和2*1的小方块&#xff0c;我们需要用这些方块填满收纳盒&#xff0c;请问我们有多少种不同的方法填满这个收纳盒 分析&…...

Oracle查询语句中做日期加减运算

在Oracle中&#xff0c;可以使用日期函数来实现日期的加减。 若想在日期上加上一定的天数&#xff0c;可以使用"INTERVAL"关键字。例如&#xff0c;如果要将一个日期加上3天&#xff0c;可以使用以下代码&#xff1a; SELECT SYSDATE INTERVAL 3 DAY FROM DUAL; …...

Unity贝塞尔曲线的落地应用-驱动飞行特效

前言 本文教你怎么用贝塞尔曲线驱动一个飞行特效 中间点的准备 开放一些可以给策划配置的变量 startPos flyEffect.transform.position; var right (GetAimPoistion(targetActor) - flyEffect.transform.position).x > 0?1:-1; midPos startPos new Vector3(righ…...

VTK——设置交互样式上的鼠标回调函数

函数介绍 VTKPointPickerInteractorStyle是一个自定义的交互样式类&#xff0c;它是VTK库中vtkInteractorStyleTrackballCamera类的子类。VTK&#xff08;Visualization Toolkit&#xff09;是一个开源的&#xff0c;跨平台的库&#xff0c;用于处理、渲染和视觉化科学数据。它…...

Flutter实现动画列表AnimateListView

由于业务需要&#xff0c;在打开列表时&#xff0c;列表项需要一个从右边飞入的动画效果&#xff0c;故封装一个专门可以执行动画的列表组件&#xff0c;可以自定义自己的动画&#xff0c;内置有水平滑动&#xff0c;缩放等简单动画。花里胡哨的动画效果由你自己来定制吧。 功…...

【LeetCode-中等题】236. 二叉树的最近公共祖先

文章目录 题目方法一&#xff1a;后序遍历 回溯 题目 方法一&#xff1a;后序遍历 回溯 解题的核心就是&#xff1a;采用后序遍历 讨论p&#xff0c;q是否在当前的root的两边&#xff0c;如在两边则返回当前节点root 如何不在两边&#xff0c;只要出现一个节点等于p或者q就…...

如何拼接两个视频在一起?

如何拼接两个视频在一起&#xff1f;在度过一个美好周末的时候&#xff0c;我和朋友一起拍摄了两组视频&#xff0c;准备将两个视频合并成一个并发布到朋友圈。这个想法非常棒&#xff0c;但是我在第一步就遇到了麻烦&#xff1a;如何将这两个视频拼接在一起&#xff1f;这听起…...

Programming abstractions in C阅读笔记:p130-p131

《Programming Abstractions In C》学习第52天&#xff0c;p130-p131&#xff0c;总结如下&#xff1a; 一、技术总结 1. pig latin game 通过pig latin game掌握字符复制&#xff0c;指针遍历等操作。 /** 输入&#xff1a;字符串&#xff0c;这里采用书中坐着自定义的get…...

如何在Windows本地快速搭建SFTP文件服务器,并通过端口映射实现公网远程访问

文章目录 1. 搭建SFTP服务器1.1 下载 freesshd服务器软件1.3 启动SFTP服务1.4 添加用户1.5 保存所有配置 2 安装SFTP客户端FileZilla测试2.1 配置一个本地SFTP站点2.2 内网连接测试成功 3 使用cpolar内网穿透3.1 创建SFTP隧道3.2 查看在线隧道列表 4. 使用SFTP客户端&#xff0…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

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

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

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...