当前位置: 首页 > news >正文

C++递归实现验证⼆叉搜索树

C++递归实现验证⼆叉搜索树

文章目录

  • C++递归实现验证⼆叉搜索树
    • 题目链接
    • 题目描述
    • 解题思路
    • C++算法代码:

题目链接

98. 验证二叉搜索树 - 力扣(LeetCode)

题目描述

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

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

  • 节点的左⼦树只包含⼩于当前节点的数。
  • 节点的右⼦树只包含⼤于当前节点的数。
  • 所有左⼦树和右⼦树⾃⾝必须也是⼆叉搜索树。

解题思路

利用中序遍历;

后序遍历按照左⼦树、根节点、右⼦树的顺序遍历⼆叉树的所有节点,通常⽤于⼆叉搜索树相关题⽬。

算法思路:

如果⼀棵树是⼆叉搜索树,那么它的中序遍历的结果⼀定是⼀个严格递增的序列。

因此,我们可以初始化⼀个⽆穷⼩的全区变量,⽤来记录中序遍历过程中的前驱结点。那么就可以在
中序遍历的过程中,先判断是否和前驱结点构成递增序列,然后修改前驱结点为当前结点,传⼊下⼀
层的递归中。

算法流程:

  1. 初始化⼀个全局的变量**prev,⽤来记录中序遍历过程中的前驱结点的val**;

  2. 中序遍历的递归函数中

a.设置递归出⼝:root==nullptr的时候,返回true

b. 先递归判断左⼦树是否是⼆叉搜索树,⽤**retleft**标记;

c.然后判断当前结点是否满⾜⼆叉搜索树的性质,⽤**retcur**标记:

  • 如果当前结点的**val⼤于prev,说明满⾜条件,retcur改为true**;
  • 如果当前结点的val⼩于等于**prev,说明不满⾜条件,retcur改为false**;

d.最后递归判断右⼦树是否是⼆叉搜索树,⽤**retright**标记;

  1. 只有当**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直接运行样例&#xff0c;于是自己新建了一个springboot项目&#xff0c;主要使用了下面的一些依赖用来运行官方样例 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache…...

PSRAM伪静态RAM芯片APS6404L

PSRAM伪静态RAM能结合SRAM和DRAM的优点&#xff0c;即容量大,又接口驱动简单&#xff0c;PSRAM接口和SRAM一样简单&#xff0c;驱动简单&#xff1b;而存储形式则和DRAM一样&#xff0c;容量远大于SRAM&#xff0c;介于SRAM和DRAM之间。 PSRAM厂家也有很多,以AP用的最多。最常…...

低级语言汇编真的各个面不如汇编吗?

今日话题&#xff0c;低级语言汇编真的各个面不如C语言吗&#xff1f;C语言因其可移植性、开发效率和可读性而在各领域广泛使用&#xff0c;市场占有率极高。然而&#xff0c;汇编语言在特定场景下仍然具有独特优势&#xff0c;稳固地占据一席之地。如果你对这方面感兴趣&#…...

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循环&#xff0c;吧edge index里面的位置填充1&#xff1a; imp…...

JavaSE19——file文件类

file文件类 在 Java File 类是 java.io 包中唯一代表磁盘文件本身的对象 File 类不能访问文件内容本身&#xff0c;如果需要访问文件内容本身&#xff0c;则需要使用输入/输出流。 File(String path)&#xff1a;如果 path 是实际存在的路径&#xff0c;则该 File 对象表示的…...

mongodb记录

MongoDB导入导出和备份的命令工具从4.4版本开始不再自动跟随数据库一起安装&#xff0c;而是需要自己手动安装。 mongodump 不是内部或外部命令&#xff0c;也不是可运行的程序 下载mongodb命令工具 下载zip格式&#xff0c;解压后把bin目录下的文件全部复制粘贴到你MongoDB安…...

Go语言:数组和切片

Python中的数组(这里指的是List类型)及其切片Slice基本相同&#xff0c;但在Go语言中这两者差别很大。 1 数组 Go语言中的数组(Array)存放的是长度固定、类型固定并且存储位置连续的一系列元素。 1.1 声明 Go语言中数组的声明方式如下&#xff1a; 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本来就是一张噪点图 云的扰动不能太大&#xff0c;将Scale调小&#xff0c;并将InputMin调整为0 形成这样一张扰动图 扰动需要根据材质在世界的位置进行调整&#xff0c;所以Position需要加上WorldPosition 材质在不同世界位置&#xff0c;噪点不同 除以一个数&#…...

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鲲鹏应用创新大赛广东赛区三等奖

近期&#xff0c;2023鲲鹏应用创新大赛广东赛区暨广东省信息技术应用创新产业联盟创新大赛圆满落幕&#xff0c;Coremail凭借“基于鲲鹏CPU的邮件网关一体机解决方案”&#xff0c;荣获“金融行业方向”三等奖。 ​ 鲲鹏凌粤 展翅湾区 本届大赛广东区域赛以“鲲鹏凌粤 展翅湾…...

Spark On Hive原理和配置

目录 一、Spark On Hive原理 &#xff08;1&#xff09;为什么要让Spark On Hive&#xff1f; 二、MySQL安装配置&#xff08;root用户&#xff09; &#xff08;1&#xff09;安装MySQL &#xff08;2&#xff09;启动MySQL设置开机启动 &#xff08;3&#xff09;修改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…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...

基于Uniapp的HarmonyOS 5.0体育应用开发攻略

一、技术架构设计 1.混合开发框架选型 &#xff08;1&#xff09;使用Uniapp 3.8版本支持ArkTS编译 &#xff08;2&#xff09;通过uni-harmony插件调用原生能力 &#xff08;3&#xff09;分层架构设计&#xff1a; graph TDA[UI层] -->|Vue语法| B(Uniapp框架)B --&g…...

MySQL基本操作(续)

第3章&#xff1a;MySQL基本操作&#xff08;续&#xff09; 3.3 表操作 表是关系型数据库中存储数据的基本结构&#xff0c;由行和列组成。在MySQL中&#xff0c;表操作包括创建表、查看表结构、修改表和删除表等。本节将详细介绍这些操作。 3.3.1 创建表 在MySQL中&#…...