Day111 | 灵神 | 二叉树 | 验证二叉搜索树
Day111 | 灵神 | 二叉树 | 验证二叉搜索树
98.验证二叉搜索树
98. 验证二叉搜索树 - 力扣(LeetCode)
方法一:前序遍历
递归函数传入合法的左右边界,只有当前结点是合法的边界,才是二叉搜索树,否则就返回false
对于左子树就传入当前结点的左边界,和当前结点的值作为右边界,从而验证左子树是一颗二叉搜索树
对于右子树就传入当前结点的右边界,和当前结点的值作为左边界,从而验证右子树是一颗二叉搜索树
只有当前结点符合条件并且左右子树也都是二叉搜索树才会返回true
灵神前序遍历代码:
class Solution {
public:bool isValidBST(TreeNode* root, long long left = LLONG_MIN, long long right = LLONG_MAX) {if (root == nullptr) {return true;}long long x = root->val;return left < x && x < right &&isValidBST(root->left, left, x) &&isValidBST(root->right, x, right);}
};
复杂度分析
- 时间复杂度:O(n),其中 n 为二叉搜索树的节点个数。
- 空间复杂度:O(n)。最坏情况下,二叉搜索树退化成一条链(注意题目没有保证它是平衡树),因此递归需要 O(n) 的栈空间。
方法二:中序遍历
二叉树搜索树的中序遍历是一个有序序列,记录前一个值,如果当前结点的值比前一个值小就是false
class Solution {
public:TreeNode *pre=nullptr;bool tra(TreeNode *t){if(t==nullptr)return true;bool l=tra(t->left);if(pre!=nullptr)if(t->val<=pre->val)return false;pre=t;bool r=tra(t->right);return l&&r;}bool isValidBST(TreeNode* root) {return tra(root);}
};
灵神中序遍历代码:
class Solution {long long pre = LLONG_MIN;
public:bool isValidBST(TreeNode* root) {if (root == nullptr) {return true;}if (!isValidBST(root->left) || root->val <= pre) {return false;}pre = root->val;return isValidBST(root->right);}
};
复杂度分析
- 时间复杂度:O(n),其中 n 为二叉搜索树的节点个数。
- 空间复杂度:O(n)。最坏情况下,二叉搜索树退化成一条链(注意题目没有保证它是平衡树),因此递归需要 O(n) 的栈空间。
方法三:后序遍历
灵神后序遍历代码:
class Solution {pair<long long, long long> dfs(TreeNode* node) {if (node == nullptr) {return {LLONG_MAX, LLONG_MIN};}auto[l_min, l_max] = dfs(node->left);auto[r_min, r_max] = dfs(node->right);long long x = node->val;// 也可以在递归完左子树之后立刻判断,如果发现不是二叉搜索树,就不用递归右子树了if (x <= l_max || x >= r_min) {return {LLONG_MIN, LLONG_MAX};}return {min(l_min, x), max(r_max, x)};}public:bool isValidBST(TreeNode* root) {return dfs(root).second != LLONG_MAX;}
};
复杂度分析
- 时间复杂度:O(n),其中 n 为二叉搜索树的节点个数。
- 空间复杂度:O(n)。最坏情况下,二叉搜索树退化成一条链(注意题目没有保证它是平衡树),因此递归需要 O(n) 的栈空间。
灵神点评
- 前序遍历在某些数据下不需要递归到叶子节点就能返回(比如根节点左儿子的值大于根节点的值,左儿子就不会继续往下递归了),而中序遍历和后序遍历至少要递归到一个叶子节点。从这个角度上来说,前序遍历是最快的。
- 中序遍历很好地利用了二叉搜索树的性质,使用到的变量最少。
- 后序遍历的思想是最通用的,即自底向上计算子问题的过程。想要学好动态规划的话,请务必掌握自底向上的思想。
相关文章:
Day111 | 灵神 | 二叉树 | 验证二叉搜索树
Day111 | 灵神 | 二叉树 | 验证二叉搜索树 98.验证二叉搜索树 98. 验证二叉搜索树 - 力扣(LeetCode) 方法一:前序遍历 递归函数传入合法的左右边界,只有当前结点是合法的边界,才是二叉搜索树,否则就返回…...
软考-软件设计师中级备考 13、刷题 数据结构
倒计时17天时间不多了,数据库、UML、等知识点有基础直接略过,法律全靠考前的一两天刷题,英语直接放弃。 一、数据结构:链表、栈、队列、数组、哈希表、树、图 1、关于链表操作,说法正确的是: A)新增一个头…...
【5G通信】天线调整
在天线工程中,机械下倾角、电子下倾角和数字下倾角是调整天线波束指向的不同技术手段,其核心区别在于实现方式和灵活性: 1. 机械下倾角(Mechanical Downtilt) 定义:通过物理调整天线的安装角度,…...
Kafka的Log Compaction原理是什么?
Kafka的Log Compaction(日志压缩)是一种独特的数据保留策略,其核心原理是保留每个key的最新有效记录。以下是关键原理分点说明: 1. 键值保留机制 通过扫描所有消息的key,仅保留每个key对应的最新value值。例如&#…...
嵌入式面试八股文(十四)·内存管理机制、优先级继承机制以及优先级翻转
目录 1. 内存管理算法(五种内存管理机制) 1.1 heap_1.c 1.2 heap_2.c 1.3 heap_3.c 1.4 heap_4.c 1.5 heap_5.c 1.6 总结 2. STM32通知寄存器有哪些? 2.1 核心寄存器组(Cortex-M) 2.2 特殊功能寄存…...
深度剖析:可视化如何重塑驾驶舱信息交互模式
为什么你开车时总觉得“信息太多却抓不住重点”? 今天的汽车早已不是单纯的交通工具,而是一个高度集成的信息终端。从导航、油耗、胎压到自动驾驶提示,各种数据不断涌进驾驶舱。 但问题也随之而来: 关键信息被淹没在一堆图标里…...
app根据蓝牙名字不同,匹配不同的产品型号,显示对应的UI界面
在开发一个 App 时,如果希望根据蓝牙设备名称(Bluetooth Name)的不同,自动匹配不同的产品型号,并显示对应的 UI 界面,可以按照以下思路来实现: ✅ 功能目标 扫描并连接蓝牙设备;获取…...
数据结构 --- 栈
1.栈的初始化 2.入栈 3.出栈 4.取出栈顶元素 5.获取栈中有效元素个数 6.栈的销毁 栈:⼀种特殊的线性表,其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作 的⼀端称为栈顶,另⼀端称为栈底。栈中的数据元素遵守后进先…...
37-算法打卡-栈与队列-滑动窗口最大值-leetcode(239)-第三十七天
1 题目地址 239. 滑动窗口最大值 - 力扣(LeetCode)239. 滑动窗口最大值 - 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑…...
【原创分享】魔音变声器内含超多语音包实时变声
魔音变声器,一款专业的调音变声器软件 亲测可使用所有功能[真棒] 去除所有广告 ————————————【下 载 地 址】———————————— 【获取方法1】:https://pan.xunlei.com/s/VOP_TXtKNlevTgYvIlxmmJquA1?pwd8vpi# ————————————【下 …...
数据结构(一)——线性表的顺序表示和实现
一、线性表的定义 由n(n>0)个数据特性相同的元素构成的有限序列称为线性表,(n0)的时候被称为空表。 一个数据元素可以是简单的一个数据,一个符号,也可以是复杂的若干个数据项的组合。 二、线性表的类型定义 s线性表是由n(n≥0)个相同类…...
Winform(12.控件讲解)
ChildForm窗口: ChildForm代码: using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms; namespac…...
Python 10天冲刺 《元编程(Meta-programming)》
Python 的元编程(Meta-programming)是指在程序运行期间动态生成、修改或操作代码的技术。它允许开发者通过代码控制代码的行为,从而实现灵活、可扩展和抽象化的编程模式。Python 提供了多种元编程工具,包括装饰器、元类、动态导入…...
Android开发-创建、运行、调试App工程
在移动应用开发的世界里,Android平台凭借其开放性和广泛的设备支持,成为了许多开发者的选择。而要成为一名合格的Android开发者,掌握如何创建、运行以及调试应用程序是必不可少的基础技能。本文将详细介绍如何使用Android Studio完成这些任务…...
系统级编程(二):通过读取PE文件获取EXE或者DLL的依赖
PE文件 Windows的PE文件(Portable Executable)是一种专为Windows操作系统设计的标准可执行文件格式,用于存储和管理可执行程序、动态链接库(DLL)、驱动程序等二进制文件。PE文件格式自Windows NT 3.1引入以来,已成为Windows平台上所有可执行文件的标准格式,并广泛应用于…...
Linux主机时间设置操作指南及时间异常影响
一、Linux主机时间设置命令操作指南 1. 查看当前系统时间与时区 查看当前时间与时区:timedatectl # 显示详细时间与时区信息(systemd系统适用) date # 查看当前系统时间 hwclock --show # 查看硬件时…...
GPS定位方案
目录 一、常用的GPS定位方案包括: 二、主流品牌及热销型号 三、常用GPS算法及核心逻辑: 一、基础定位算法 二、高精度算法 三、辅助优化算法 四、信号处理底层算法 四、基本原理(想自己写算法的琢磨一下原理) 一、常用的GP…...
应对联网汽车带来的网络安全挑战
数字化加速正在彻底改变全球各行各业,而汽车行业更是走在了前列。目前,全球自动驾驶汽车保有量约为4860万辆,预计到2024年将增长至5420万辆。 智能汽车的崛起无疑令人兴奋,但也带来了一系列问题。为了保护客户免受新的威胁,汽车行业必须做出一系列考量:针对自动驾驶、网…...
人工智能与生命科学的深度融合:破解生物医学难题,引领未来科技革命
引言 随着人工智能技术的飞速发展,生命科学领域迎来了前所未有的变革。从药物研发到疾病预测,从个性化医疗到基因组学,AI的深度融入不仅加速了生物医学的进步,还在多个领域打破了传统科学研究的局限,开创了新的医学前沿…...
DeepSeek智能时空数据分析(七):4326和3857两种坐标系有什么区别?各自用途是什么?
序言:时空数据分析很有用,但是GIS/时空数据库技术门槛太高 时空数据分析在优化业务运营中至关重要,然而,三大挑战仍制约其发展:技术门槛高,需融合GIS理论、SQL开发与时空数据库等多领域知识;空…...
Qt/C++面试【速通笔记七】—Qt中为什么new QWidget不需要手动调用delete?
在Qt的开发中,管理内存是一个非常重要的话题,特别是在使用QWidget这类窗口组件时,很多开发者会遇到一个问题:“为什么我使用new QWidget创建的窗口对象不需要手动调用delete进行销毁?”。 1. 父子关系机制:…...
Super-vlan
Super VLAN(VLAN聚合)的理论与配置 1. 基本概念 Super VLAN(超级VLAN)是一种VLAN聚合技术,主要用于解决传统VLAN划分中IP地址浪费的问题。其核心思想是将多个Sub VLAN(子VLAN)聚合到一个Super …...
C——函数
一、函数的概念 数学中我们其实就⻅过函数的概念,⽐如:⼀次函数 y kx b ,k和b都是常数,给⼀个任意的 x,就得到⼀个y值。 其实在C语⾔也引⼊函数(function)的概念,有些翻译为&…...
5.6刷题并查集
P1551 亲戚 #include<bits/stdc.h> using namespace std; const int N 5010; int f[N]; int find(int x){if(f[x] x)return x;return f[x] find(f[x]); } void solve(){int n, m, p; cin >> n >> m >> p;for(int i 1; i < n; i)f[i] i;for(in…...
pcl平面投影
// 创建一个系数为XY0,Z1的平面pcl::ModelCoefficients::Ptr coefficients (new pcl::ModelCoefficients ());coefficients->values.resize (4);coefficients->values[0] coefficients->values[1] 0;coefficients->values[2] 1.0;coefficients->values[3] 0…...
Linux远程管理
如何查看ip 如何使用vim编辑器 如何设置网络信息 远程访问 一:网络管理 (1)获取计算机的网络信息 基本语法: windows ipconfig ifconfig enS33: f1agS4163<UP,BR0ADCAST,RUNNING,MULTICAST> mtu 1500 inet…...
如何添加或删除极狐GitLab 项目成员?
极狐GitLab 是 GitLab 在中国的发行版,关于中文参考文档和资料有: 极狐GitLab 中文文档极狐GitLab 中文论坛极狐GitLab 官网 项目成员 (BASIC ALL) 成员是有权访问您的项目的用户和群组。 每个成员都有一个角色,这决定了他们在项目中可以…...
2025年服务器技术全景解析:量子计算、液冷革命与未来生态构建
2025年服务器技术全景解析:量子计算、液冷革命与未来生态构建 一、量子计算:从实验室到产业化的跨越 1. 中国量子计算产业化突破 • 本源量子“悟空”超导计算机: 搭载72位自主超导量子芯片“悟空芯”,支持198个量子比特…...
Vue3+ Vite + Element-Plus + TypeScript 从0到1搭建
一环境准备 二vite 项目初始化 按照 🍃Vite 官方文档 - 搭建第一个 Vite 项目 说明,执行以下命令完成 vue 、typescirpt 模板项目的初始化 npm init vitelatest vue3-element-admin --template vue-tsvue3-element-admin: 自定义的项目名称 vue-ts &am…...
如何对 Redis 进行水平扩展和垂直扩展以应对微服务流量的增长?
核心概念: 垂直扩展 (Scale Up): 提升单个节点的性能。简单来说就是给现有的 Redis 服务器增加更多的 CPU 、内存、更快的存储(SSD)或更高的网络带宽。水平扩展 (Scale Out): 增加更多节点来分担负载。这意味着部署多个 Redis 实例ÿ…...
PyCharm 加载不了 conda 虚拟环境,不存在的
#工作记录 前言 在开发过程中,PyCharm 无法加载 Conda 虚拟环境是常见问题。 在不同情况下,“Conda 可执行文件路径”的指定可能会发生变化,不会一尘不变,需要灵活处置。 以下是一系列解决此问题的经验参考。 检查 Conda 安装…...
Matlab/Simulink的一些功能用法笔记(4)
水一篇帖子 01--MATLAB工作区的保护眼睛颜色设置 默认的工作区颜色为白色 在网上可以搜索一些保护眼睛的RGB颜色参数设置 在MATLAB中按如下设置: ①点击预设 ②点击颜色,点击背景色的三角标符号 ③点击更多颜色,找到RGB选项 ④填写颜色参数…...
OS7.【Linux】基本指令入门(6)
目录 1.zip和unzip 配置指令 使用 两个名词:打包和压缩 打包 压缩 Linux下的操作演示 压缩和解压缩文件 压缩和解压缩目录 -d选项 2.tar Linux下的打包和压缩方案简介 czf选项 xzf选项 -C选项 tzf选项 3.bc 4.uname 不带选项的uname -a选项 -r选项 -v选项…...
便捷OCR文字识别软件推荐
软件介绍 此次要介绍的是一款OCR识别软件。 核心功能及特点 这款小巧的OCR识别软件,功能简洁,操作方便,只需进行截图,随后就能自动识别文字内容。并且,它具备离线使用的特性,这一特点使得它非常适合在不联…...
【中间件】brpc_基础_栈管理
文章目录 BRPC bthread栈管理1 简介2 关键数据结构2.1 栈描述符 (bthread_stack_t)2.2 栈池 (StackPool) 3 核心操作3.1 栈分配 (bthread_stack_alloc)3.2 栈释放 (bthread_stack_dealloc)3.3 栈切换支持 4 性能优化5 安全性设计6 跨平台实现6.1 Linux6.2 Windows 7 应用场景8 …...
Linux 硬盘和光驱系统管理
一、硬盘与目录的容量 [rootwww ~]# df [-ahikHTm] [目录或档名] 选项与参数: -a :列出所有的档案系统,包括系统特有的 /proc 等档案系统; -k :以 KBytes 的容量显示各档案系统; -m :以 MByt…...
分库分表后复杂查询的应对之道:基于DTS实时性ES宽表构建技术实践
1 问题域 业务发展的初期,我们的数据库架构往往是单库单表,外加读写分离来快速的支撑业务,随着用户量和订单量的增加,数据库的计算和存储往往会成为我们系统的瓶颈,业界的实践多数采用分而治之的思想:分库…...
[三分钟]性能测试工具JMeter入门: 下载安装JMeter并设置中文;JMeter基本使用流程
文章目录 1.下载并打开JMeter2.设置JMeter中文3.JMeter基本使用流程 Apache JMeter 是 Apache 组织基于 Java 开发的压力测试工具。 JMeter 支持多种协议和技术,如 HTTP、HTTPS、FTP、JDBC、SOAP、REST、JMS 等。它不仅可以用于性能测试,还可以用于功能测…...
StableDiffusionWebUI的AI绘图AI绘视频详细使用教程+报错排坑
概述 这里是官方的最原始的体积最小的StableDiffusionWebUI的下载及其使用教程,已经帮你们把坑都排完了,本教程适合开发者、程序员自己折腾,源码体积只有1.8M。 从0安装到绘图 1.环境 Python与Git环境: 安装Python3.10.0 >…...
Flutter 合并 ‘dot-shorthands‘ 语法糖,Dart 开始支持交叉编译
最近在 Dart 在 main 3.9 合并了一项名为 「dot-shorthands」 的语法糖提议,该提议主要是为了简化开发过程中的相关静态固定常量的写法,通过上下文类型推断简化枚举值和静态成员的访问: 简单来说,就是在之前你可能需要写 SomeEnum…...
貌似我的ollama加载的模型被下载了两份?终于搞懂原理了。
文章目录 背景ollama的模型默认会被放在哪儿呢?什么是homedir?ollama服务直接ollama serve如何修改保存模型文件的路径?背景 如果你想以最快的方式,部署本地的大模型,那么ollama无疑是最合适的选择之一。我其实linux用的不多。之前一直是在windows上部署的ollama。后来有…...
【HarmonyOS 5】鸿蒙用户头像编辑功能实践
【HarmonyOS 5】鸿蒙用户头像编辑功能实践 一、前言 1、应用背景 在鸿蒙化开发过程中,我们发现最基本常见的功能–用户头像的编辑,实现方式和Android与IOS有极大的不同。 在实际开发和调研的过程中,我们发现并总结了鸿蒙隐私处理与业内Android和IOS的差异性。发现隐私保…...
VTK|结合qt创建通用按钮控制显隐(边框、坐标轴、点线面)
文章目录 增加边框BoundingBox添加addBoundingBox添加BoundingBox控制按钮点击按钮之后的槽函数 添加坐标轴增加点线面显隐控制按钮添加控制点线面显隐的按钮到三维显示界面控制面显示槽函数控制线显示槽函数控制点显示槽函数 增加边框BoundingBox 增加边框BoundingBox并通过按…...
Python Cookbook-7.3 在 Pickling 的时候压缩
任务 你想以一种压缩的方式来 pickle 一般的 Python 对象。 解决方案 标准库模块 cPickle 和 gzip提供了所需的功能;你只需以适当的方式将它们粘合起来即可: import cPickle,gzip def save(filename,*objects):将对象存为压缩过的磁盘文件fil gzip.open(filename,wb)for o…...
合并两个有序链表 - 简单
************* C topic: 21. 合并两个有序链表 - 力扣(LeetCode) ************* Give the topic an inspection. Hi, guys, how is your holiday break? I went to 黄山 in the past few days. The mount Huang is really beautiful. 天都峰 is real…...
手写 Vue 源码 === Effect 机制解析
目录 核心概念 响应式效果的实现 依赖收集的具体流程 为什么使用全局变量? 嵌套 effect 的处理 总结 Vue3 的响应式系统核心在于跟踪依赖并在数据变化时触发更新。effect.ts文件实现了这一机制的核心部分,下面我们来梳理其中的关键思路。 核心概念…...
《AI大模型应知应会100篇》第49篇:大模型应用的成本控制策略
第49篇:大模型应用的成本控制策略 🧾 摘要 随着AI大模型的广泛应用,其高昂的部署与运行成本成为企业面临的一大挑战。本文将从技术架构、资源优化、业务模式等多个维度出发,系统性地讲解如何在保障服务质量的前提下,实…...
利用Ollama部署DeepSeek模型
利用Ollama部署DeepSeek模型 最近,DeepSeek作为一款高效的推理模型受到了广泛关注,但在使用网页版过程中,总是遇到服务器繁忙,因此尝试在本地部署DeepSeek来使用。 一、Ollama安装指南 Ollama是一个开源的AI大模型部署工具&…...
数字孪生储能充电站,实现智慧能源设施全景管控
图扑将储能充电站的电池组、充电桩、配电系统等设备进行数字孪生,通过实时接入充放电数据、设备状态及能耗信息,以三维可视化界面直观呈现储能动态、电力调度与运维场景,助力运营方优化资源配置、预判设备故障,推动储能充电设施高…...
MCP服务发展现状的有趣发现
MCP服务发展现状的有趣发现 当前,MCP(Model Context Protocol)在AI领域逐渐成为一个热门话题。其核心意义在于赋予大模型直接调用外部工具的能力,从而打破“数据孤岛”,实现真正的工具增强型AI。然而,在深…...