面试热题(验证二叉搜索树)

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉树

       二叉树满足以上3个条件,有些同学就会说,BST不就是左大右小么?我直接判断root.val>root.left.valroot.val<root.right.val不就可以了么?

         这样肯定是不对的,因为BST左小右大的特性是指root.val要比左子树的所有节点要大,要比右子树上的所有节点要小,所以只是检查两个节点当前是不够的,我们可以通过辅助函数,增加函数参数列表,在参数中携带额外信息,将下一个节点的合理取值范围传递下去,进行判断

因为root节点开始没有范围的限制,所以我们对其的边界可以最小的无穷,最大也是无穷

isValidBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);

如果当前节点不符合合法边界,直接返回false

 if(node.val<=lower||node.val>=upper){
            return false;
        }

去遍历当前节点的左子树和右子数,并更新取值范围

isValidBST(node.left,lower,node.val)&&isValidBST(node.right,node.val,upper);

结果:

       看到测试案例顿时豁然开朗,一看这种比较大的数,一看就是数值类型的问题,超出范围了,然后我们将Integer改为更大的Long,然后:

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/72515.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何使用Pycharm 快速搭建 Django 项目 (分享详细图文教程)

1. 准备工作 在开始创建Django项目之前&#xff0c;需要先确保已经安装了Python和Pycharm。并且python中已经安装好了Django依赖。 1安装python&#xff08;这里我安装使用的是python3.11.4稳定版本&#xff09; 官网下载太慢了这里直接贴网盘下载连接了&#xff0c;一起贴出py…

Linux基础知识学习

一、i.mx6ull交叉编译QT项目 1、步骤 2、安装交叉编译链 使能交叉编译链&#xff0c;使能刚安装的编译器&#xff0c;不然还是老版本的 source /opt/fsl-imx-x11/4.1.15-2.1.0/environment-setup-cortexa7hf-neon-poky-linux-gnueabi 3、命令行交叉编译QT项目 wandzhangwa…

机器学习笔记:李宏毅 stable diffusion

1 基本框架 ①&#xff1a;文字变成向量 ②&#xff1a;喂入噪声文字encoder&#xff0c;产生中间产物 ③&#xff1a;decoder 还原图片 2 text encoder 这张图越往右下表示效果越好&#xff0c;可以看到text encoder尺寸越大&#xff0c;对后续生成图片的增益越多 3 评价图…

京东秋招攻略,备考在线测评和网申笔试

京东秋招简介 伴随着社会竞争越来越激烈&#xff0c;人们投递简历的岗位也变得越来越多元&#xff0c;而无论人们的选择面变成何样&#xff0c;那些知名度较高的企业&#xff0c;永远都备受关注&#xff0c;只要其一发布招聘公告&#xff0c;总有人第一时间踊跃报名。而作为这…

threejs纹理的使用

实现地板的效果&#xff0c;需要导入3张图片&#xff0c;第一种样式&#xff0c;第二种&#xff0c;木板间的间隙&#xff0c;第三种&#xff0c;木板的粗细图片。先注册一个物体属性&#xff0c;在物体属性上加上图片&#xff0c;注册代码如下图&#xff1a; const floorMat …

windows server 2016 搭建使用 svn 服务器教程

参考教程&#xff1a; https://zhuanlan.zhihu.com/p/428552058 https://blog.csdn.net/weixin_33897722/article/details/85602029 配置环境 windows server 2016 远程服务器公网 ip 安装 SVN 服务端 下载 svn 服务端安装包&#xff1a;https://www.visualsvn.com/download…

Spring boot中的线程池-ThreadPoolTaskExecutor

一、jdk的阻塞队列&#xff1a; 二、Spring boot工程的有哪些阻塞队列呢&#xff1f; 1、默认注入的ThreadPoolTaskExecutor 视频解说&#xff1a; 线程池篇-springboot项目中的service层里简单注入ThreadPoolTaskExecutor并且使用_哔哩哔哩_bilibili 程序代码&#xff1a;…

2023国赛数学建模C题思路分析

文章目录 0 赛题思路1 竞赛信息2 竞赛时间3 建模常见问题类型3.1 分类问题3.2 优化问题3.3 预测问题3.4 评价问题 4 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 竞赛信息 全国大学生数学建模…

计算机网络-专业术语

计算机网络-专业术语 实体 实体:任何可发送或接收信息的硬件或软件进程 对等实体:收发双方相同层次中的实体 协议 控制两个对等实体进行逻辑通信的规则的集合 协议三要素 语法 定义所交换的信息的格式 是用户数据与控制信息的结构和格式 语义 定义收发双方所需要完成的操作…

(MySQL经验)之MySQL单表行数最好低于2000w

作为在后端开发&#xff0c;是不是经常听到过&#xff0c;mysql 单表最好不要超过 2000w,单表超过 2000w 就要考虑数据迁移了&#xff0c;表数据都要到 2000w &#xff0c;查询速度变得贼慢。 1、建表操作 建一张表 CREATE TABLE person( id int NOT NULL AUTO_INCREMENT PRI…

华为云MetaStudio多模态数字人进展及挑战介绍

// 编者按&#xff1a;数字人作为AI能力集大成者&#xff0c;涉及计算机视觉、计算机图形学、语音处理、自然语言处理等技术&#xff0c;正在金融、政务、传媒、电商等领域应用越来越广。LiveVideoStackCon 2023 上海站邀请到华为云的李明磊为我们介绍华为云在数字人领域当前…

阿里云服务器竞价实例是什么意思?优缺点对比_选择攻略

腾讯云服务器CVM计费模式分为包年包月、按量计费和竞价实例&#xff0c;什么是竞价实例&#xff1f;竞价实例和按量付费相类似&#xff0c;优势是价格更划算&#xff0c;缺点是云服务器实例有被自动释放风险&#xff0c;腾讯云服务器网来详细说下什么是竞价实例&#xff1f;以及…

论文详解 ——《SNR-Aware Low-light Image Enhancement》

文章目录 Abstract1.Introduction2. Related Work3. Our Method3.1 Long- and Short-range Branches3.2 SNR-based Spatially-varying Feature Fusion3.3 SNR-guided Attention in Transformer3.4 Loss Function 4. Experiments4.1. Datasets and Implementation Details4.2 Co…

STM32 LL库开发

一、STM32开发方式 标准库开发&#xff1a;Standard Peripheral Libraries&#xff0c;STDHAL库开发&#xff1a;Hardware Abstraction Layer&#xff0c;硬件抽象层LL库开发&#xff1a;Low-layer&#xff0c;底层库 二、HAL库与LL库开发对比 ST在推行HAL库的时候&#xff0c;…

阿里云预装LAMP应用导致MySQL不显示访问密码如何解决

&#x1f600;前言 本篇博文是关于阿里云云服务器ECS部署MySQL过程中出现的一下坑&#xff0c;希望能够帮助到您&#x1f60a; &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家…

APP外包开发的iOS开发语言

学习iOS开发需要掌握Swift编程语言和相关的开发工具、框架和技术。而学习iOS开发需要时间和耐心&#xff0c;尤其是对于初学者。通过坚持不懈的努力&#xff0c;您可以逐步掌握iOS开发技能&#xff0c;构建出功能丰富、优质的移动应用。今天和大家分享学习iOS开发的一些建议方法…

Ubuntu安装bfloat16==1.1出现问题 error: subprocess-exited-with-error

报错 error: subprocess-exited-with-error python setup.py bdist_wheel did not run successfully. 解决方法 确保你的系统上已经安装了 C/C 编译器&#xff08;如 gcc、g&#xff09;。 如果你使用的是 Linux 系统&#xff0c;你可以使用包管理器来安装它们。命令如下 u…

R语言中的函数24:Combinat:combn(), permn()

介绍 combinat中的combn()和permn()函数可以得到所有的排列组合的情况 combn()函数 combn(x, m, funNULL, simplifyTRUE, …)x – 组合的向量源m – 要取的元素的数量fun – 应用于每个组合的函数(可能为空)simplify – 逻辑的&#xff0c;如果是FALSE&#xff0c;返回一个列…

小程序具体开发

window 导航栏 属性名类型默认值作用navigationBarTitleText string字字符串导航栏标题内容navigationBarBackgroundColorHexcolor#000000设置导航栏背景颜色&#xff08;比如荧黄色 #ffa&#xff09;navigationBarTextStylestringwhite设置导航栏标题的颜色&#xff08;仅含有…

视频网站如何选择国外服务器?

​ 视频网站如何选择国外服务器? 地理位置&#xff1a;选择靠近目标用户群体的国外服务器位置是至关重要的。若用户主要集中在中国以外的地区&#xff0c;因您应选择位于用户所在地附近的服务商&#xff0c;以确保视频的传输速度。 带宽和速度&#xff1a;选择带宽足够且方便升…