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

LeetCode 算法:验证二叉搜索树 c++

原题链接🔗:验证二叉搜索树
难度:中等⭐️⭐️

题目

给你一个二叉树的根节点 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

题解

  1. 解题思路:

验证一棵二叉树是否为二叉搜索树(BST)是算法面试中常见的问题。二叉搜索树具有以下性质:

  1. 若任意节点的左子树不为空,则左子树上所有节点的值均小于它的节点值。
  2. 若任意节点的右子树不为空,则右子树上所有节点的值均大于它的节点值。
  3. 任意节点的左、右子树也可能有空二叉树,并且都同时为空。
  4. 左子树和右子树也分别为二叉搜索树。

以下是验证二叉搜索树的几种解题思路:

  1. 中序遍历
    二叉搜索树的中序遍历结果应该是一个递增的序列。因此,可以通过中序遍历来验证二叉树是否为BST。

    • 对二叉树进行中序遍历,将遍历结果存储在一个数组中。
    • 检查数组中的元素是否是递增的。

这种方法的时间复杂度是O(n),空间复杂度也是O(n),因为需要存储所有的节点值。

  1. 递归检查
    使用递归函数,同时检查当前节点的值是否在允许的范围内。

    • 定义一个变量lowerupper来存储当前节点允许的最小值和最大值,初始时可以是负无穷和正无穷。
    • 在递归函数中,首先检查当前节点的值是否在lowerupper之间。
    • 然后递归地对左子树和右子树调用函数,同时更新lowerupper的值。

这种方法的时间复杂度是O(n),因为它只需要遍历一次所有节点,空间复杂度是O(h),其中h是树的高度,因为递归栈的深度。

  1. 迭代法
    使用迭代法代替递归,可以避免递归带来的栈溢出问题,特别是对于非常深的树。

    • 使用一个栈来存储节点,从根节点开始,按照二叉树的遍历顺序(例如先序、中序或后序)将节点压入栈中。
    • 同时维护一个变量来记录前一个节点的值。
    • 当迭代到下一个节点时,检查它是否符合BST的顺序性。

这种方法的时间复杂度同样是O(n),空间复杂度也是O(n),因为最坏情况下,栈可能需要存储所有的节点。

  1. Morris遍历
    Morris遍历是一种不需要额外空间的遍历方法,可以用于验证BST。

    • 使用Morris遍历遍历二叉树,同时检查节点的值是否递增。
    • Morris遍历通过在树中添加临时指针来实现,不需要使用栈或数组。

这种方法的时间复杂度是O(n),空间复杂度是O(1),因为它不需要额外的存储空间。

每种方法都有其优缺点,你可以根据具体情况选择最合适的方法。例如,如果树非常深,递归可能会导致栈溢出,此时可以使用迭代法或Morris遍历。如果需要额外的空间不是问题,中序遍历是一个简单直观的方法

递归法

  1. 复杂度:时间复杂度是O(n),因为它只需要遍历一次所有节点,空间复杂度是O(h),其中h是树的高度,因为递归栈的深度。
  2. c++ demo
#include <iostream>
#include <limits>struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:bool isValidBST(TreeNode* root) {return validate(root, std::numeric_limits<long>::min(), std::numeric_limits<long>::max());}private:bool validate(TreeNode* node, long min, long max) {if (!node) return true; // 空节点是有效的// 检查当前节点的值是否在合适的范围内if (node->val <= min || node->val >= max) return false;// 递归地验证左子树和右子树// 左子树的所有值必须小于当前节点的值// 右子树的所有值必须大于当前节点的值return validate(node->left, min, node->val) &&validate(node->right, node->val, max);}
};int main() {Solution solution;// 构建一个示例二叉搜索树TreeNode* root = new TreeNode(2);root->left = new TreeNode(1);root->right = new TreeNode(3);// 验证二叉搜索树bool result = solution.isValidBST(root);std::cout << (result ? "Valid BST" : "Invalid BST") << std::endl;// 清理分配的内存(注意:在实际应用中,应该使用智能指针来自动管理内存)delete root->left;delete root->right;delete root;return 0;
}
  • 输出结果:

Valid BST

  1. 代码仓库地址:isValidBST

相关文章:

LeetCode 算法:验证二叉搜索树 c++

原题链接&#x1f517;&#xff1a;验证二叉搜索树 难度&#xff1a;中等⭐️⭐️ 题目 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左 子树 只包含 小于 当前节点的数。节点的右子树只包含 大于…...

SpringBoot优点达项目实战:获取系统配置接口(三)

SpringBoot优点达项目实战&#xff1a;获取系统配置接口&#xff08;二&#xff09; 文章目录 SpringBoot优点达项目实战&#xff1a;获取系统配置接口&#xff08;二&#xff09;1、查看接口2、查看数据库3、代码实现1、创建实体类SysConfig2、创建返回数据的vo3、创建control…...

【C语言】字符/字符串+内存函数

目录 Ⅰ、字符函数和字符串函数 1 .strlen 2.strcpy 3.strcat 4.strcmp 5.strncpy 6.strncat 7.strncmp 8.strstr 9.strtok 10.strerror 11.字符函数 12. 字符转换函数 Ⅱ、内存函数 1 .memcpy 2.memmove 3.memcmp Ⅰ、字符函数和字符串函数 1 .strlen 函数原型&#xff1a;…...

上下文管理器在Python中的妙用

更多Python学习内容&#xff1a;ipengtao.com Python上下文管理器是一个非常强大的工具&#xff0c;它能够帮助开发者在特定代码块前后自动执行特定的操作&#xff0c;常用于资源管理&#xff0c;如文件操作、数据库连接和锁定等。本文将详细介绍Python上下文管理器的概念、使用…...

【PWN · TcachebinAttack | UAF】[2024CISCN · 华中赛区] note

一道简单的tcache劫持 一、题目 二、思路 存在UAF&#xff0c;libc版本2.31&#xff0c;经典菜单题 1.通过unsorted-bin-attack来leak-libc 2.通过uaf打tcache-bin-attack劫持__free_hook实现getshell 三、EXP from pwn import * context(archamd64,log_leveldebug)ioproce…...

Java数据脱敏

数据脱敏 敏感数据在存储过程中为是否为明文, 分为两种 落地脱敏: 存储的都是明文, 返回之前做脱敏处理不落地脱敏: 存储前就脱敏, 使用时解密, 即用户数据进入系统, 脱敏存储到数据库中, 查询时反向解密 落地脱敏 这里指的是数据库中存储的是明文数据, 返回给前端的时候脱…...

【Java Web】三大域对象

目录 一、域对象概述 二、三大域对象 三、域对象使用相关API 一、域对象概述 一些可用于存储数据和传递数据的对象被称为域对象&#xff0c;根据传递数据范围的不同&#xff0c;我们称之为不同的域&#xff0c;不同的域对象代表不同的域&#xff0c;共享数据的范围也不同。 二、…...

【Linux】进程信号_3

文章目录 八、进程信号2. 信号的保存3. 信号的处理 未完待续 八、进程信号 2. 信号的保存 实际执行信号的处理动作称为信号递达(Delivery) 信号从产生到递达之间的状态,称为信号未决(Pending)。 进程可以选择阻塞 (Block )某个信号。 被阻塞的信号产生时将保持在未决状态,直到…...

LongRAG:利用长上下文大语言模型提升检索生成效果

一、前言 前面我们已经介绍了多种检索增强生成 (RAG) 技术&#xff0c;基本上在保证数据质量的前提下&#xff0c;检索增强生成&#xff08;RAG&#xff09;技术能够有效提高检索效率和质量&#xff0c;相对于大模型微调技术&#xff0c;其最大的短板还是在于有限的上下文窗口…...

go中的方法 func-----数据类型

本文是java学习者学go种产生的容易记混点的笔记,所以有其他编译语言的基础更好 go的方法有点像js 基础 func main() {fmt.Println("Starting")var p *string new(string)*p "hello world"demo : "demo"fmt.Println(*&demo) //这样既然也…...

408计算机网络--物理层

一、物理层概述 物理层是干嘛使得&#xff1f; 物理层解决如何在连接各种计算机的传输媒体上传输数据比特流&#xff0c;而不是指具体的传输媒体。 物理层主要任务是确定与传输媒体接口有关的一些特性。定义标准可以理解为插排上的两孔三孔 机械特性&#xff1a;定义物理连接…...

十年,亚马逊云科技合作伙伴网络开启AI新征程

“十年之前&#xff0c;你不认识我&#xff0c;我不认识你&#xff0c;因为云计算我们携手并肩&#xff1b;十年之后&#xff0c;我们仍是伙伴&#xff0c;更是朋友&#xff0c;因为人工智能再次起程。”这就是今天的亚马逊云科技与其合作伙伴的真实写照。 2024年是亚马逊云科技…...

基于Spring Boot的在线医疗咨询平台的设计与实现【附源码】

基于Spring Boot的在线医疗咨询平台的设计与实现 Design and implementation of the computer hardware mall based on Spring Boot Candidate&#xff1a; Supervisor&#xff1a; April 20th, 2024 学位论文原创性声明 本人郑重声明&#xff1a;所呈交的论文是本人在导师…...

星坤Type-A连接器:创新快充技术,引领电子连接!

快速发展的电子时代&#xff0c;消费者对电子设备的性能和便利性有着更高的要求。特别是在充电和数据传输方面&#xff0c;快充技术和高速传输已成为市场的新宠。中国星坤公司推出的Type-A连接器系列&#xff0c;以其卓越的性能和创新的设计&#xff0c;满足了市场对高效、稳定…...

入门JavaWeb之 Response 下载文件

web 服务器接收到客户端的 http 请求 针对这个请求&#xff0c;分别创建一个代表请求的 HttpServletRequest 对象&#xff0c;代表响应的 HttpServletResponse 对象 获取客户端请求过来的参数&#xff1a;HttpServletRequest 给客户端响应一些信息&#xff1a;HttpServletRe…...

Java自定义注解校验token并直接返回给前端状态

自定义注解 CheckToken import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;Target(ElementType.METHOD) Retention(RetentionPolicy.RUNTIME) public int…...

C++ | Leetcode C++题解之第200题岛屿数量

题目&#xff1a; 题解&#xff1a; class Solution { private:void dfs(vector<vector<char>>& grid, int r, int c) {int nr grid.size();int nc grid[0].size();grid[r][c] 0;if (r - 1 > 0 && grid[r-1][c] 1) dfs(grid, r - 1, c);if (r …...

Linux安全配置

Linux系统审计信息有&#xff1a;系统启动日志&#xff08;boot.log&#xff09;、记录用户执行命令日志&#xff08;acct/pacct&#xff09;、记录使用su命令的使用&#xff08;sulog&#xff09;、记录当前登录的用户信息&#xff08;utmp&#xff09;、用户每次登陆和退出信…...

vue实现不预览PDF的情况下打印pdf文件

前景&#xff1a;默认情况&#xff0c;实现打印需要根据预览的内容进行打印。 但是当只有打印按钮存在&#xff0c;不预览文件内容的情况下&#xff0c;实现打印的话&#xff0c;可以通过后端接口返回服务器上PDF的地址,前端通过隐藏的iframe标签中src可实现预览功能 主要是根据…...

C++ | Leetcode C++题解之第199题二叉树的右视图

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<int> rightSideView(TreeNode* root) {unordered_map<int, int> rightmostValueAtDepth;int max_depth -1;stack<TreeNode*> nodeStack;stack<int> depthStack;nodeStack.push(ro…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...