LeetCode hot 100—验证二叉搜索树

题目

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

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

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

示例

示例 1:

输入:root = [2,1,3]
输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

分析

二叉搜索树具有以下特性:对于树中的每个节点,其左子树中的所有节点值都小于该节点的值,而其右子树中的所有节点值都大于该节点的值,并且左子树和右子树本身也必须是有效的二叉搜索树。

递归法

可以采用递归的方法来遍历整棵二叉树,在遍历过程中,为每个节点设置一个合理的取值范围,通过检查每个节点的值是否在这个范围内,以及递归地检查其左右子树是否也满足二叉搜索树的条件,从而判断整棵树是否为有效的二叉搜索树。

时间复杂度:O(n), n 是二叉树中的节点数

空间复杂度:O(h),h 是二叉树的高度

class Solution {
public:bool isValidBST(TreeNode* root) {return isValidBSTHelper(root, LONG_MIN, LONG_MAX);}
private:bool isValidBSTHelper(TreeNode* node, long minVal, long maxVal) {if (node == nullptr) {return true;}// 检查当前节点的值是否在合法范围内if (node->val <= minVal || node->val >= maxVal) {return false;}// 递归检查左子树和右子树return isValidBSTHelper(node->left, minVal, node->val) &&isValidBSTHelper(node->right, node->val, maxVal);}
};    

中序遍历法

对二叉搜索树进行中序遍历,得到的节点值序列是一个严格递增的序列。因此,我们可以通过中序遍历二叉树,并在遍历过程中检查节点值是否始终保持递增来判断该二叉树是否为有效的 BST。

时间复杂度:O(n), n 是二叉树中的节点数

空间复杂度:O(h),h 是二叉树的高度

class Solution {
private:long long prev = LLONG_MIN;  // 记录前一个节点的值,初始化为极小值
public:bool isValidBST(TreeNode* root) {if (root == nullptr) {return true;}// 递归遍历左子树if (!isValidBST(root->left)) {return false;}// 检查当前节点值是否大于前一个节点值if (root->val <= prev) {return false;}prev = root->val;  // 更新前一个节点值// 递归遍历右子树return isValidBST(root->right);}
};

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

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

相关文章

ccfcsp3402矩阵重塑(其二)

//矩阵重塑&#xff08;其二&#xff09; #include<iostream> using namespace std; int main(){int n,m,t;cin>>n>>m>>t;int c[10000][10000];int s0,sum0;int d[10000],k[100000];for(int i0;i<n;i){for(int j0;j<m;j){cin>>c[i][j];d[s…

MCP和Function Calling的区别

文章目录 1、什么是MCP1.1、定义和特点1.2、架构和工作原理3.3、MCP 的主要优势 2、什么是Function Calling3、MCP和Function Calling的区别4、总结 &#x1f343;作者介绍&#xff1a;双非本科大四网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;前三年专注于Java领域…

裂缝识别系统 Matlab GUI设计

使用说明 裂缝识别系统 Matlab GUI设计 &#xff0c;运行环境Matlab2023b及以上&#xff1b; 一种基于MATLAB图形用户界面&#xff08;GUI&#xff09;的裂缝自动识别系统&#xff0c;该系统利用数字图像处理技术实现裂缝图像的预处理&#xff0c;集成均衡化、噪声滤波、对比…

【源码分析】Nacos实例注册流程分析-事件驱动框架

【踩坑记录】 本人下载的Nacos 服务端版本是2.3.2&#xff0c;在开始进行源码编译便遇到问题&#xff0c;下面是各个问题记录 源码大量爆红 在最开始用Idea加载Maven项目的时候&#xff0c;发现项目中大量的代码爆红&#xff0c;提示其类或者包不存在&#xff0c;后来结果查…

51单片机指令系统入门

目录 基本概念讲解 一、机器指令​ 二、汇编指令​ &#xff08;一&#xff09;汇编指令的一般格式 &#xff08;二&#xff09;按字节数分类的指令 三、高级指令 总结​ 基本概念讲解 指令是计算机&#xff08;或单片机&#xff09;中 CPU 能够识别并执行的基本操作命令…

mysql5.x和mysql8.x查看和设置隔离级别

MySQL的隔离级别 级别标志值描述读未提交READ-UNCOMMITTED0存在脏读、不可重复读、幻读的问题读已提交READ-COMMITTED1解决脏读的问题&#xff0c;存在不可重复读、幻读的问题可重复读REPEATABLE-READ2mysql 默认级别&#xff0c;解决脏读、不可重复读的问题&#xff0c;存在幻…

【函数式编程】【C#/F#】第四讲:单子与函子 - 抽象的编程模式

在第二讲中我们探讨了一个诚实的函数应该要做到什么事&#xff0c;并运用了一种方法&#xff0c;让我们可以去准确的描述数据。 不过有一种情况让我们始料未及&#xff0c;例如网站需要收集一些信息&#xff0c;但有些信息不是必须的&#xff0c;是可有可无的。如果我们要去准…

【vue2 + Cesium】使用Cesium、添加第三方地图、去掉商标、Cesium基础配置、地图放大缩小事件、获取可视区域、层级、高度

参考文章&#xff1a; vue2 使用 cesium 篇【第一篇】 vue2 使用 cesium 【第二篇-相机视角移动添加模型】 vue2 项目模版&#xff1a; vue2-common 安装 cesium npm install cesium --save这个就很简单&#xff0c;只需要一句简简单单的命令就可以实现在 vue 项目中安装 ce…

vllm-openai多服务器集群部署AI模型

服务器配置是两台ubantu系统电脑,每台电脑安装两张4090-48G显存的显卡,共计192G显存。 服务器1 服务器2 准备工作: 1.两台电脑都已经安装了docker 2.两台电脑都已经安装了nvidia驱动 参考vllm官方资料 https://docs.vllm.ai/en/latest/serving/distributed_serving.html…

【电源】斩波电路

文章目录 前言定义概念 缩写降压斩波电路使用步骤总结参考文献 前言 进行大创项目开发的学习 bilibili 定义概念 缩写 斩波电路&#xff1a;分为降压&#xff0c;电荷泵&#xff0c;升压&#xff0c;升降压&#xff0c;Cuk&#xff0c;Speic&#xff0c;Zeta 等等 降压斩…

Hadoop集群组成

&#xff08;一&#xff09;Hadoop的组成 对普通用户来说&#xff0c; Hadoop就是一个东西&#xff0c;一个整体&#xff0c;它能给我们提供无限的磁盘用来保存文件&#xff0c;可以使用提供强大的计算能力。 在Hadoop3.X中&#xff0c;hadoop一共有三个组成部…

c++基础知识-图论进阶

一、拓扑排序 1、基础知识 1&#xff09;什么是拓扑排序 对一个有向无环图G进行拓扑排序&#xff0c;是将G中所有顶点排成一个线性序列&#xff0c;使得图中任意一对顶点u和v&#xff0c;若&#xff0c;则u在线性序列中出现在v之前。 2&#xff09;拓扑排序的操作方法 重复执行…

从Scaling Laws中解析大模型训练的边际递减临界点

前言 当我们拆解GPT-4到DeepSeek的演进路径&#xff0c;会发现一个反直觉的真相&#xff1a;​AI的智能跃迁不依赖参数堆砌&#xff0c;而取决于对"结构-能量-信息"三元关系的精准把控。就像人类大脑在进化中通过皮层折叠而非单纯增大体积来实现智能突破&#xff0c…

Word 小黑第20套

对应大猫21 特定一页设为横向 上下用分页符

【从0到1搞懂大模型】RNN基础(4)

先说几个常用的可以下载数据集的地方 平台&#xff1a;kaggle&#xff08;https://www.kaggle.com/datasets&#xff09; 和鲸社区&#xff08;https://www.heywhale.com/home&#xff09; 阿里天池&#xff08;https://tianchi.aliyun.com/&#xff09; 其他&#xff1a;海量公…

openEuler24.03 LTS下安装MySQL8

前提条件 拥有openEuler24.03 LTS环境&#xff0c;可参考&#xff1a;Vmware下安装openEuler24.03 LTS 步骤 卸载原有mysql及mariadb sudo systemctl stop mysql mysqld 2>/dev/null sudo rpm -qa | grep -i mysql\|mariadb | xargs -n1 sudo rpm -e --nodeps 2>/dev/…

如何在Odoo 18中实现OWL通知服务

如何在Odoo 18中实现OWL通知服务 OWL&#xff08;Odoo Web Library&#xff09;是Odoo的前端框架&#xff0c;用于构建现代化的动态响应式用户界面。在早期版本中&#xff0c;Odoo 前端设计与开发使用的是诸如 QWeb 这类较为老旧的框架&#xff0c;而随着 Odoo 每发布一个新版本…

Unet nn-Unet

Unet && nn-Unet&#xff1a; 文章题目&#xff1a;U-Net: Convolutional Networks for Biomedical Image Segmentation 代码&#xff1a;https://lmb.informatik.uni-freiburg.de/people/ronneber/u-net/ 文章题目&#xff1a;nnU-Net: Self-adapting Framework for U…

【扩散模型入门】Latent Diffusion

1. 概述 扩散模型为公众所知的一个主要原因是Stable Diffusion(SD)的推出展现出了远超以往的图像合成效果,而SD的主要技术就是Latent Diffusion Model(LDM)。 实际上,LDM的核心idea非常简单: 为了确保生成质量,LDM尽可能提升去噪模型的规模。提升模型规模往往也会同步…

搭建主从服务器

任务需求 客户端通过访问 www.nihao.com 后&#xff0c;能够通过 dns 域名解析&#xff0c;访问到 nginx 服务中由 nfs 共享的首页文件&#xff0c;内容为&#xff1a;Very good, you have successfully set up the system. 各个主机能够实现时间同步&#xff0c;并且都开启防…