C++递归实现验证⼆叉搜索树
C++递归实现验证⼆叉搜索树
文章目录
- C++递归实现验证⼆叉搜索树
- 题目链接
- 题目描述
- 解题思路
- C++算法代码:
题目链接
98. 验证二叉搜索树 - 力扣(LeetCode)
题目描述
给你⼀个⼆叉树的根节点root,判断其是否是⼀个有效的⼆叉搜索树。
有效⼆叉搜索树定义如下:
- 节点的左⼦树只包含⼩于当前节点的数。
- 节点的右⼦树只包含⼤于当前节点的数。
- 所有左⼦树和右⼦树⾃⾝必须也是⼆叉搜索树。
解题思路
利用中序遍历;
后序遍历按照左⼦树、根节点、右⼦树的顺序遍历⼆叉树的所有节点,通常⽤于⼆叉搜索树相关题⽬。
算法思路:
如果⼀棵树是⼆叉搜索树,那么它的中序遍历的结果⼀定是⼀个严格递增的序列。
因此,我们可以初始化⼀个⽆穷⼩的全区变量,⽤来记录中序遍历过程中的前驱结点。那么就可以在
中序遍历的过程中,先判断是否和前驱结点构成递增序列,然后修改前驱结点为当前结点,传⼊下⼀
层的递归中。算法流程:
初始化⼀个全局的变量**
prev,⽤来记录中序遍历过程中的前驱结点的val**;中序遍历的递归函数中 :
a.设置递归出⼝:
root==nullptr的时候,返回true;b. 先递归判断左⼦树是否是⼆叉搜索树,⽤**
retleft**标记;c.然后判断当前结点是否满⾜⼆叉搜索树的性质,⽤**
retcur**标记:
- 如果当前结点的**
val⼤于prev,说明满⾜条件,retcur改为true**;- 如果当前结点的val⼩于等于**
prev,说明不满⾜条件,retcur改为false**;d.最后递归判断右⼦树是否是⼆叉搜索树,⽤**
retright**标记;
- 只有当**
retleft、retcur和retright都是true的时候,才返回true**。
C++算法代码:
class Solution { long prev = LONG_MIN; public: bool isValidBST(TreeNode* root) { if(root == nullptr) return true; bool left = isValidBST(root->left); // 剪枝 if(left == false) return false; bool cur = false; if(root->val > prev) cur = true; // 剪枝 if(cur == false) return false; prev = root->val; bool right = isValidBST(root->right); return left && right && cur; } };
相关文章:
C++递归实现验证⼆叉搜索树
C递归实现验证⼆叉搜索树 文章目录 C递归实现验证⼆叉搜索树题目链接题目描述解题思路C算法代码: 题目链接 98. 验证二叉搜索树 - 力扣(LeetCode) 题目描述 给你⼀个⼆叉树的根节点root,判断其是否是⼀个有效的⼆叉搜索树。 有效⼆…...
♥ uniapp 环境搭建
♥ uniapp 环境搭建 开发uniapp需要用到的工具有两个: 1、用到的平台和地址: 需要了解的几个平台以及地址: (1)微信公众平台 https://mp.weixin.qq.com/ (2)微信开发文档 https://develo…...
京东商品链接获取京东商品评论数据(用 Python实现京东商品评论信息抓取),京东商品评论API接口,京东API接口
在网页抓取方面,可以使用 Python、Java 等编程语言编写程序,通过模拟 HTTP 请求,获取京东多网站上的商品详情页面评论内容。在数据提取方面,可以使用正则表达式、XPath 等方式从 HTML 代码中提取出有用的信息。值得注意的是&#…...
docker容器中安装ROS1/ROS2(不用配任何环境,10分钟搞定)
默认电脑已经安装了docker,没安装看这篇文章Docker 安装 (完整详细版) ROS和docker各种结合看官方文档 dockerTutorials 在OSRF中拉取想要的 ROS 版本 docker 镜像 网址为 拉取命令在这里 我是安装noetic版本,因为这个兼容比较多现有的工程 docker pul…...
如何解决ssh登录报错WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
原因: 当两个设备第一次进行链接时,会在~/.ssh/konwn_hosts 中将被连接设备的公钥信息进行保存,后续再次链接时OpenSSH会核对公钥来进行一个简单的验证 然而有时候被链接的那台设备系统被重装、IP 冲突等原因,会导致公钥信息没…...
Mysql5.7安装配置详细图文教程(msi版本)
博主介绍:✌全网粉丝5W,全栈开发工程师,从事多年软件开发,在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战,博主也曾写过优秀论文,查重率极低,在这方面有丰富的经验…...
运行dl4j-examples的主要一些依赖
直接从git获取dl4j-examples后本地无法用IJ直接运行样例,于是自己新建了一个springboot项目,主要使用了下面的一些依赖用来运行官方样例 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache…...
PSRAM伪静态RAM芯片APS6404L
PSRAM伪静态RAM能结合SRAM和DRAM的优点,即容量大,又接口驱动简单,PSRAM接口和SRAM一样简单,驱动简单;而存储形式则和DRAM一样,容量远大于SRAM,介于SRAM和DRAM之间。 PSRAM厂家也有很多,以AP用的最多。最常…...
低级语言汇编真的各个面不如汇编吗?
今日话题,低级语言汇编真的各个面不如C语言吗?C语言因其可移植性、开发效率和可读性而在各领域广泛使用,市场占有率极高。然而,汇编语言在特定场景下仍然具有独特优势,稳固地占据一席之地。如果你对这方面感兴趣&#…...
PyG edge index 转换回 邻接矩阵
PyG的edge index形式是 [ ( n o d e 1 , n o d e 2 ) , ( n o d e 1 , n o d e 3 ) . . . ] [(node_1,node_2), (node_1, node_3)...] [(node1,node2),(node1,node3)...]这种edge pair。 naive 直接for循环,吧edge index里面的位置填充1: imp…...
JavaSE19——file文件类
file文件类 在 Java File 类是 java.io 包中唯一代表磁盘文件本身的对象 File 类不能访问文件内容本身,如果需要访问文件内容本身,则需要使用输入/输出流。 File(String path):如果 path 是实际存在的路径,则该 File 对象表示的…...
mongodb记录
MongoDB导入导出和备份的命令工具从4.4版本开始不再自动跟随数据库一起安装,而是需要自己手动安装。 mongodump 不是内部或外部命令,也不是可运行的程序 下载mongodb命令工具 下载zip格式,解压后把bin目录下的文件全部复制粘贴到你MongoDB安…...
Go语言:数组和切片
Python中的数组(这里指的是List类型)及其切片Slice基本相同,但在Go语言中这两者差别很大。 1 数组 Go语言中的数组(Array)存放的是长度固定、类型固定并且存储位置连续的一系列元素。 1.1 声明 Go语言中数组的声明方式如下: arr1 : [5]string{"…...
OPENCV 闭运算实验示例代码morphologyEx()函数
void CrelaxMyFriendDlg::OnBnClickedOk() {hdc this->GetDC()->GetSafeHdc();// TODO: 在此添加控件通知处理程序代码string imAddr "c:/Users/actorsun/Pictures/";string imAddr1 imAddr"rice.png";Mat relax, positive;relax imread(imAddr1…...
UE4 体积云制作 学习笔记
首先Noise本来就是一张噪点图 云的扰动不能太大,将Scale调小,并将InputMin调整为0 形成这样一张扰动图 扰动需要根据材质在世界的位置进行调整,所以Position需要加上WorldPosition 材质在不同世界位置,噪点不同 除以一个数&#…...
visual studio编译QtAV
1.1 依赖环境 第一种方法: 下载编译好的ffmpeg-3.4.2-win64-dev和ffmpeg-3.4.2-win64-shared,解压得到 D:\qt-workspace\ffmpeg-3.4.2-win64-dev D:\qt-workspace\ffmpeg-3.4.2-win64-shared 第二种方法: QtAV官方有提供编译好的依赖库 QtAV-depends-windows-x86%2Bx64.7…...
喜报!CACTER邮件安全网关荣获2023鲲鹏应用创新大赛广东赛区三等奖
近期,2023鲲鹏应用创新大赛广东赛区暨广东省信息技术应用创新产业联盟创新大赛圆满落幕,Coremail凭借“基于鲲鹏CPU的邮件网关一体机解决方案”,荣获“金融行业方向”三等奖。 鲲鹏凌粤 展翅湾区 本届大赛广东区域赛以“鲲鹏凌粤 展翅湾…...
Spark On Hive原理和配置
目录 一、Spark On Hive原理 (1)为什么要让Spark On Hive? 二、MySQL安装配置(root用户) (1)安装MySQL (2)启动MySQL设置开机启动 (3)修改MySQL…...
驱动第十天
...
工作中常用的git命令,千万不能忘
1、设置当前分支为默认分支: git branch –set-upstream-toorigin/master 2、To push the current branch and set the remote as upstream, use: git push --set-upstream origin eds_enhancement 3、同步远程分支 git remote update --prune [remote] 4、Remo…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
