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

LeetCode刷题--- 验证二叉搜索树

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

http://t.csdnimg.cn/ZxuNL个人专栏:力扣递归算法题 http://t.csdnimg.cn/ZxuNL

                  【C++】  http://t.csdnimg.cn/c9twt


前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


注意:这道题目涉及到二叉搜索树的内容 ,若有不懂的可以参考下面这篇文章 

数据结构:二叉搜索树-CSDN博客


验证二叉搜索树

题目链接:验证二叉搜索树

题目:

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

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

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

示例 1:

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

示例 2:

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

提示:

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

解法

题目解析

题目没什么好说的,就是给我们一颗二叉树,判断它是否为二叉搜索树

二叉搜索树有如下特性:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

 算法原理思路讲解   

解法一:

依靠二叉搜索树的特性:中序遍历为有序

思路:创建一个全局变量 v ,中序遍历整个二叉树,然后再判断 v 是否有序即可


解法二:

解法一虽然也可以通过,但是我们没有必要连续插入

思路:

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

算法流程:
  1. 初始化⼀个全局的变量 prev,⽤来记录中序遍历过程中的前驱结点的 val
  2. 中序遍历的递归函数中:
    (1)设置递归出⼝:root == nullptr 的时候,返回 true;
    (2)先递归判断左⼦树是否是⼆叉搜索树,⽤ left 标记;
    (3)然后判断当前结点是否满⾜⼆叉搜索树的性质,⽤ cur 标记:
                    1)如果当前结点的 val ⼤于 prev,说明满⾜条件,cur 改为 true;
                    2)如果当前结点的 val ⼩于等于 prev,说明不满⾜条件,cur 改为 false;
    (4)最后递归判断右⼦树是否是⼆叉搜索树,⽤ right 标记;
  3. 只有当 left、 cur 和 right 都是 true 的时候,才返回 true。

以上思路就讲解完了,大家可以先自己先做一下 


代码实现

解法一

  • 时间复杂度:O(n),其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次,因此时间复杂度为 O(n)。
  • 空间复杂度:O(n),其中 n 为二叉树的节点个数。vector最多存储 n 个节点,因此需要额外的 O(n) 的空间。
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> v;void dfs(TreeNode* root){if (root == nullptr){return;}dfs(root->left);v.push_back(root->val);dfs(root->right);}bool isValidBST(TreeNode* root) {bool flag = true;dfs(root);for (int i = 1; i < v.size(); i++){if (v[i-1] >= v[i]){flag = false;}}return flag;}
};

解法二

  • 时间复杂度:O(n),其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次,因此时间复杂度为 O(n)。
  • 空间复杂度:O(n),其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,即二叉树的高度。最坏情况下二叉树为一条链,树的高度为 n ,递归最深达到 n 层,故最坏情况下空间复杂度为 O(n) 。
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
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;}
};

相关文章:

LeetCode刷题--- 验证二叉搜索树

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 http://t.csdnimg.cn/ZxuNL个人专栏&#xff1a;力扣递归算法题 http://t.csdnimg.cn/ZxuNL 【C】 http://t.csdnimg.cn/c9twt 前言&#xff1a;这个专栏主要讲述递归递归、搜索与回溯算法&#x…...

go-zero 开发入门-加法客服端示例

定义 RPC 接口文件 接口文件 add.proto 的内容如下&#xff1a; syntax "proto3"; package add;// 当 protoc-gen-go 版本大于 1.4.0 时需加上 go_package&#xff0c;否则编译报错“unable to determine Go import path for” option go_package "./add&qu…...

Python 快速入门——基础语法

python 的语法逻辑完全靠缩进&#xff0c;建议缩进 4 个空格。 如果是顶级代码&#xff0c;那么必须顶格书写&#xff0c;哪怕只有一个空格也会有语法错误。 下面示例中&#xff0c;满足 if 条件要输出两行内容&#xff0c;这两行内容必须都缩进&#xff0c;而且具有相同的缩进…...

EasyRecovery2024苹果电脑mac破解版安装包下载

EasyRecovery是一款操作安全、价格便宜、用户自主操作的非破坏性的只读应用程序&#xff0c;它不会往源驱上写任何东西&#xff0c;也不会对源驱做任何改变。它支持从各种各样的存储介质恢复删除或者丢失的文件&#xff0c;其支持的媒体介质包括&#xff1a;硬盘驱动器、光驱、…...

Git常用命令大全

1.强制推送&#xff08;慎用&#xff0c;除非你认为其他冲突等可以丢弃 或者不是很重要&#xff09; git push -- force2.创建文件等小命令 touch a // 创建一个a文件 echo 1234 >> a // 把1234这个内容放入a文件 cat a // 打开a文件 读取出a文件中的内容 mkdir test /…...

vue项目本地正常运行,打包到线上时无法访问js等资源

nginx配置错误&#xff0c;如&#xff1a; location /aaa/ {gzip on;gzip_static on;try_files $uri $uri/ /aaa/index.html;alias /home/ec2-user/data/aaa/;#这里必须以斜杆结束&#xff0c;否则就会报错}前端配置文件错误&#xff0c;如&#xff1a; config/index.js文件的b…...

计网Lesson10 - 网络层之IP协议分析

文章目录 网络层协议IPv4 数据报格式IPv4 数据报首部格式版本&#xff08;Version&#xff09;首部长度&#xff08;Header Length&#xff09;区分服务&#xff08;Differentiated Services Field&#xff09;可选字段填充总长度&#xff08;Total Length&#xff09;标识、标…...

LangChain 25: SQL Agent通过自然语言查询数据库sqlite

LangChain系列文章 LangChain 实现给动物取名字&#xff0c;LangChain 2模块化prompt template并用streamlit生成网站 实现给动物取名字LangChain 3使用Agent访问Wikipedia和llm-math计算狗的平均年龄LangChain 4用向量数据库Faiss存储&#xff0c;读取YouTube的视频文本搜索I…...

Redis生产实战-热key、大key解决方案、数据库与缓存最终一致性解决方案

生产环境中热 key 处理 热 key 问题就是某一瞬间可能某条内容特别火爆&#xff0c;大量的请求去访问这个数据&#xff0c;那么这样的 key 就是热 key&#xff0c;往往这样的 key 也是存储在了一个 redis 节点中&#xff0c;对该节点压力很大 那么对于热 key 的处理就是通过热…...

可惜+悲伤+唉=emmo...

拟合曲线&#xff1a; 参考论文&#xff1a;黄河清.NURBS曲面逆向造型关键算法的研究与应用 [D].西北工业大学,2004 三次NURBS曲线控制点的计算 首先给出拟合曲线的具体步骤&#xff1a; 1、节点矢量的求解方法为&#xff1a; 采用积累弦长参数化法&#xff0c;即&#xff1…...

[gRPC实现go调用go]

1什么是RPC RPC&#xff1a;Remote Procedure Call&#xff0c;远程过程调用。简单来说就是两个进程之间的数据交互。正常服务端的接口服务是提供给用户端(在Web开发中就是浏览器)或者自身调用的&#xff0c;也就是本地过程调用。和本地过程调用相对的就是&#xff1a;假如两个…...

uniapp使用v-html调用接口,富文本图片 视频自适应大小

前端获取到后台数据 不做处理 就会出现下面问题 图片 视频超出视图显示不全 处理 //info 是富文本 <view v-ifinfo v-htmlreplaceWhite(info)></view>调用下面方法 replaceWhite(html) { // 处理富文本默认图片&#xff0c;视频大小let newContent html.replace…...

安卓MediaRecorder(2)录制源码分析

文章目录 前言JAVA new MediaRecorder() 源码分析android_media_MediaRecorder.cpp native_init()MediaRecorder.java postEventFromNativeandroid_media_MediaRecorder.cpp native_setup() MediaRecorder 参数设置MediaRecorder.prepare 分析MediaRecorder.start 分析MediaRec…...

MySql数据库全量备份脚本

#!/bin/bash# 设置数据库连接信息 DB_HOST"localhost" DB_USER"root" DB_PASS"密码" DB_NAMES("db1" "db2" "db3" "db4")# 设置备份目录 BACKUP_DIR"/home/mysql/mysql-back/everyday" # 每天…...

windows10下jdk安装

文章目录 windows10下jdk安装说明what安装包下载执行安装包验证是否安装成功 windows10下jdk安装 说明 操作系统&#xff1a;windows10 版本&#xff1a;1.8 what JDK(Java Development Kit) 是 Java 语言的软件开发工具包 安装包下载 https://www.oracle.com/java/techn…...

Centos7防火墙及端口开启

1、防火墙 1.1、查看防火墙是否开启 systemctl status firewalld 1.2、开启防火墙 firewall-cmd --list-ports 1.3、重启防火墙 firewall-cmd --reload 2、端口 2.1、查看所有已开启的端口号 firewall-cmd --list-ports 2.2、手动开启端口 启动防火墙后&#xff0c;默认没有开…...

vue开发,axios网络请求框架基本用法和封装

axios安装 npm install axiosaxios基本用法 默认的get请求&#xff0c;参数用params追加&#xff0c;多个参数通过json对象的方式&#xff0c;例如params:‘{type:“home”,page:1}’ axios({url: https://api.videolog.net.cn/baidu/token,params: }).then(value > {co…...

对比SPI、UART、I2C通信的区别与应用

SPI、UART、I2C通信是常用的数字通信协议&#xff0c;它们在不同的场景下有不同的应用。下面&#xff0c;我将分别介绍它们的特点、区别与应用。 SPI通信 SPI通信是一种串行同步通信协议&#xff0c;它的全称为“Serial Peripheral Interface”。SPI通信是一种单主多从的通信方…...

CentOS7安装MySQL8.0

一、使用Yum安装 1. 使用wget下载MySQL的rpm包 wget https://repo.mysql.com//mysql80-community-release-el7-3.noarch.rpm2. 安装下载好的rpm包 yum localinstall mysql80-community-release-el7-3.noarch.rpm 3. 安装mysql&#xff08;该步可能出现问题&#xff09; yum…...

【Go<—>Java】gRPC测试注意事项

在做go和Java之间gRPC调用之前需要完成以下两项工作&#xff1a; go语言版本的gRPC调用&#xff0c;实现server端和client端Java语言版本的gRPC调用&#xff0c;实现server端和client端 由于gRPC是跨语言的通信协议&#xff0c;所以我们可以相互调用&#xff0c;有以下2种调用…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...