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…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
