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…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
