当前位置: 首页 > 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…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...