LeetCodehot 力扣热题100 验证二叉搜索树

class Solution {vector<int> nums;  // 用来存储二叉树节点值的数组
public:bool isValidBST(TreeNode* root) {inorder(root);  // 中序遍历二叉树,填充 nums 数组// 遍历 nums 数组,检查是否为严格递增序列for(int i=0; i<nums.size()-1; i++){if(nums[i] >= nums[i+1]){  // 如果当前元素不小于下一个元素,说明不是严格递增的return false;  // 不是有效的二叉搜索树}}return true;  // 如果整个数组都是严格递增的,说明是有效的二叉搜索树}private:// 中序遍历:遍历树的左子树、根节点和右子树void inorder(TreeNode* root){if(root != nullptr){  // 如果当前节点不是空节点inorder(root->left);  // 递归遍历左子树nums.push_back(root->val);  // 将当前节点的值加入 nums 数组inorder(root->right);  // 递归遍历右子树}}
};

这段代码是一个验证二叉搜索树(BST)是否有效的算法。通过中序遍历二叉树,将节点的值存储在一个数组中,然后检查数组是否是严格递增的。二叉搜索树的性质是:左子树的值小于根节点的值,右子树的值大于根节点的值,而中序遍历会得到一个按升序排列的节点值序列。

思路:

1. 中序遍历:首先我们要遍历二叉树,使用中序遍历。对于一棵合法的二叉搜索树,使用中序遍历会得到一个严格递增的节点值序列

2. 将节点值存储到数组:通过递归进行中序遍历,将每个节点的值按顺序存储到一个数组 nums 中。

3. 验证递增性:中序遍历完成后,检查 nums 数组中的值是否是严格递增的。如果有任何两个相邻的元素不满足递增条件,返回 false,表示这不是一棵有效的二叉搜索树。

4. 返回结果:如果数组是严格递增的,说明这棵树符合二叉搜索树的要求,返回 true。

运行步骤:

假设我们有以下二叉树:

      2

     / \

    1   3

1. 初始状态

• nums 数组为空。

2. 执行 inorder(root):

• 调用 inorder(2),根节点是 2。

• 递归调用 inorder(1)(左子树)。

• 在 inorder(1) 中,递归调用 inorder(null)(空左子树),然后将 1 加入 nums 数组。

• 返回并继续遍历右子树(inorder(null)),没有元素。

• 现在,nums = [1]。

• 返回 inorder(2),将 2 加入 nums 数组。

• 继续遍历右子树,调用 inorder(3)。

• 在 inorder(3) 中,递归调用 inorder(null)(空左子树),将 3 加入 nums 数组。

• 继续遍历右子树(inorder(null)),没有元素。

• 现在,nums = [1, 2, 3]。

• inorder 遍历结束后,nums = [1, 2, 3]。

3. 执行递增性检查

• nums = [1, 2, 3]。

• 遍历数组:

• 比较 nums[0] 和 nums[1],即 1 和 2,1 < 2,继续检查。

• 比较 nums[1] 和 nums[2],即 2 和 3,2 < 3,继续检查。

• 所有检查都通过,返回 true。

边界情况:

空树:如果根节点是空的,inorder 函数不会执行任何操作,nums 数组会保持为空。此时,直接返回 true,因为空树是有效的二叉搜索树。

只有一个节点的树:即使树只有一个节点,nums 数组也只会包含一个元素,严格递增性自然成立,返回 true。

时间复杂度:

中序遍历:时间复杂度是 O(n),其中 n 是树中节点的数量,因为我们遍历了每个节点一次。

数组检查:时间复杂度是 O(n),需要检查 nums 数组中的所有元素。

总的时间复杂度:O(n)。

空间复杂度:

• 我们使用了一个 nums 数组来存储树的节点值,空间复杂度是 O(n),其中 n 是树中节点的数量。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Pdf手册阅读(1)--数字签名篇

原文阅读摘要 PDF支持的数字签名&#xff0c; 不仅仅是公私钥签名&#xff0c;还可以是指纹、手写、虹膜等生物识别签名。PDF签名的计算方式&#xff0c;可以基于字节范围进行计算&#xff0c;也可以基于Pdf 对象&#xff08;pdf object&#xff09;进行计算。 PDF文件可能包…

CSS3+动画

浏览器内核以及其前缀 css标准中各个属性都要经历从草案到推荐的过程&#xff0c;css3中的属性进展都不一样&#xff0c;浏览器厂商在标准尚未明确的情况下提前支持会有风险&#xff0c;浏览器厂商对新属性的支持情况也不同&#xff0c;所有会加厂商前缀加以区分。如果某个属性…

微信小程序分包异步化

分包1引入分包2的组件或者js 引入组件&#xff1a; 主包里的pages/tabbars/tabbar1/tabbar1页面 引入分包sub1的sub1/components/sub1-component/sub1-component组件 1、分包预下载 首先在app.js定义preloadRule "preloadRule": {"pages/tabbars/tabbar1/tabb…

后端java工程师经验之谈,工作7年,mysql使用心得

mysql 工作7年&#xff0c;mysql使用心得 mysql1.创建变量2.创建存储过程2.1&#xff1a;WHILE循环2.2&#xff1a;repeat循环2.3&#xff1a;loop循环2.4&#xff1a;存储过程&#xff0c;游标2.5&#xff1a;存储过程&#xff0c;有输入参数和输出参数 3.三种注释写法4.case …

基于 GEE 利用插值方法填补缺失影像

目录 1 完整代码 2 运行结果 利用GEE合成NDVI时&#xff0c;如果研究区较大&#xff0c;一个月的影像覆盖不了整个研究区&#xff0c;就会有缺失的地方&#xff0c;还有就是去云之后&#xff0c;有云量的地区变成空值。 所以今天来用一种插值的方法来填补缺失的影像&#xf…

unity学习34:角色相关3,触发器trigger,铰链 hingejoint 等 spring joint, fixed joint

目录 1 触发的实现条件 1.1 碰撞的的实现条件 1.2 触发的实现条件 1.3 触发器trigger&#xff0c;直接拿 碰撞器collider修改下配置即可 2 触发器相关实验&#xff1a;触发开门效果 2.0 目标 2.1 player物体的属性 2.2 新建一个trigger 物体 2.3 新建一个被trigger 控…

(1/100)每日小游戏平台系列

每日小游戏平台 项目简介以及地址 准备开发一个一百天小游戏平台&#xff0c;使用Flask构建的简单游戏导航网站&#xff0c;无需登录&#xff0c;让大家在返工的同时也可以愉快的摸鱼玩耍。 每天更新一个小游戏上传&#xff0c;看看能不能坚持一百天。 这些小游戏主要使用前端…

从零到一:基于Rook构建云原生Ceph存储的全面指南(上)

文章目录 一.Rook简介二.Rook与Ceph架构2.1 Rook结构体系2.2 Rook包含组件1&#xff09;Rook Operator2&#xff09;Rook Discover3&#xff09;Rook Agent 2.3 Rook与kubernetes结合的架构图如下2.4 ceph特点2.5 ceph架构2.6 ceph组件 三.Rook部署Ceph集群3.1 部署条件3.3 获取…

第40天:Web开发-JS应用VueJS框架Vite构建启动打包渲染XSS源码泄露代码审计

#知识点 1、安全开发-VueJS-搭建启动&打包安全 2、安全开发-VueJS-源码泄漏&代码审计 一、Vue搭建创建项目启动项目 1、Vue 框架搭建->基于nodejs搭建&#xff0c;安装nodejs即可 参考&#xff1a;https://cn.vuejs.org/ 已安装18.3或更高版本的Node.js 2、Vue 创建…

DeepSeek做赛车游戏

赛车模型 2D生成图片 任意AI图片软件SD&#xff0c;MJ 图片生成3D模型 车身 车轮 场景 Rodin,Tripo和Meshy 询问deepSeek如何开发 拷贝代码 将汽车运行代码拖到汽车上 再让AI写个摄像头跟随代码 再去提问deepseek控制轮胎和一些处理细节

软考高级《系统架构设计师》知识点(一)

计算机硬件 校验码 码距&#xff1a;就单个编码A:00而言&#xff0c;其码距为1&#xff0c;因为其只需要改变一位就变成另一个编码。在两个编码中&#xff0c;从A码到B码转换所需要改变的位数称为码距&#xff0c;如A:00要转换为B:11&#xff0c;码距为2。一般来说&#xff0c;…

亚博microros小车-原生ubuntu支持系列:26手势控制小车基础运动

背景知识 手指检测&#xff1a;亚博microros小车-原生ubuntu支持系列&#xff1a;4-手部检测-CSDN博客 程序功能说明 功能开启后&#xff0c;摄像头捕获图像&#xff0c;识别手势来控制小车移动。 手势 “5”小车前进拳头小车后退手势 “1”小车向左手势 “2”小车向右 运…

OpenFeign远程调用返回的是List<T>类型的数据

在使用 OpenFeign 进行远程调用时&#xff0c;如果接口返回的是 List 类型的数据&#xff0c;可以通过以下方式处理&#xff1a; 直接定义返回类型为List Feign 默认支持 JSON 序列化/反序列化&#xff0c;如果服务端返回的是 List的JSON格式数据&#xff0c;可以直接在 Feig…

【hive】记一次hiveserver内存溢出排查,线程池未正确关闭导致

一、使用 MemoryAnalyzer软件打开hprof文件 很大有30G&#xff0c;win内存24GB&#xff0c;不用担心可以打开&#xff0c;ma软件能够生成索引文件&#xff0c;逐块分析内存&#xff0c;如下图。 大约需要4小时。 overview中开不到具体信息。 二、使用Leak Suspects功能继续…

【Docker】

一、概述 1、Docker为什么出现&#xff1f; 开发和运维两套环境&#xff0c;而环境配置十分麻烦。如在Windows上开发&#xff0c;要发布到Linux上运行。 Docker给以上问题提出解决方案&#xff1a;Java --- Jar(环境&#xff09;---打包项目带上环境&#xff08;镜像&#x…

游戏手柄Type-c方案,支持一边充电一边传输数据

乐得瑞推出LDR6023SS&#xff0c;专门针对USB-C接口手机手柄方案&#xff0c;支持手机快充&#xff0c;支持任天堂游戏机&#xff0c;PS4等设备~同时支持手机充电跟数据传输 1、概述 LDR6023SS SSOP16 是乐得瑞科技针对 USB Type-C 标准中的 Bridge 设备而开发的双 USB-C DRP …

【报错解决】Sql server 2022连接数据库时显示证书链是由不受信任的颁发机构颁发的

SSMS 20在连接Sql server 2022数据库时有如下报错&#xff1a; A connection was successfully established with the server, but then an error occurred during the login process. (provider: SSL Provider, error: 0 - 证书链是由不受信任的颁发机构颁发的。 原因是尝试使…

「vue3-element-admin」告别 vite-plugin-svg-icons!用 @unocss/preset-icons 加载本地 SVG 图标

&#x1f680; 作者主页&#xff1a; 有来技术 &#x1f525; 开源项目&#xff1a; youlai-mall ︱vue3-element-admin︱youlai-boot︱vue-uniapp-template &#x1f33a; 仓库主页&#xff1a; GitCode︱ Gitee ︱ Github &#x1f496; 欢迎点赞 &#x1f44d; 收藏 ⭐评论 …

NineData云原生智能数据管理平台新功能发布|2025年1月版

本月发布 14 项更新&#xff0c;其中重点发布 6 项、功能优化 7 项、安全性更新 1 项。 重点发布 数据库 Devops - 数据导出功能增强 支持 AWS ElastiCache 数据源&#xff1a;现已支持通过 SQL 查询语句或直接通过库表导出 AWS ElastiCache 数据&#xff0c;方便用户快速提取…

游戏引擎学习第96天

讨论了优化和速度问题&#xff0c;以便简化调试过程 节目以一个有趣的类比开始&#xff0c;提到就像某些高端餐厅那样&#xff0c;菜单上充满了听起来陌生或不太清楚的描述&#xff0c;需要依靠服务员进一步解释。虽然这听起来有些奇怪&#xff0c;但实际上&#xff0c;它反映…