验证二叉搜索数(98)
98. 验证二叉搜索树 - 力扣(LeetCode)
解法:
/*** 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:bool isValidBST(TreeNode* root) {if ((root == nullptr) ||(root->left == nullptr && root->right == nullptr)) {return true;}//考虑到Node.val 的取值范围:-2exp(31) <= Node.val <= 2exp(31) - 1,bound代表二叉搜索数一个节点需要满足的值的范围,所以搜索二叉树初始化的最小值和最大值:std::pair<int64_t, int64_t> bound = std::make_pair(int64_t(numeric_limits<int32_t>::min()) - 1, int64_t(numeric_limits<int32_t>::max()) + 1);return isValidBSTCore(root, bound);}bool isValidBSTCore(TreeNode* root, std::pair<int64_t, int64_t> bound){if (root == nullptr) {return true;}//前序遍历,先访问当前节点if (root->val > bound.first && root->val < bound.second ) {//访问左子树,以及计算其取值范围 && 访问又子树 以及计算其取值范围return isValidBSTCore(root->left, std::make_pair(bound.first, std::min(int64_t(root->val),bound.second))) && isValidBSTCore(root->right, std::make_pair(std::max(int64_t(root->val), bound.first), bound.second));}else {return false;}}
};
总结:
计算时间复杂度O(N),其空间复杂度O(N),具体算法如上述代码和注释。
相关文章:
验证二叉搜索数(98)
98. 验证二叉搜索树 - 力扣(LeetCode) 解法: /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* …...
StarRocks BE源码编译、CLion高亮跳转方法
阅读SR BE源码时,很多类的引用位置爆红找不到,或无法跳转过去,而自己的Linux机器往往缺乏各种C依赖库,配置安装比较麻烦,因此总体的思路是通过CLion远程连接SR社区已经安装完各种依赖库的Docker容器,进行编…...
数模测评:doubao1.5>deepseek-v3>gpt-o1
本次测试了当前评价最高的三款大模型doubao1.5、gpt-o1、deepseek-v3(r1崩溃),都是采用无提示词的硬核提问方式,测试视频如下。 gpto1、doubao1.5、deepseek测评 测试方式: 上传美赛六道题目文件 直接提问以下5句话: 这是一道数学…...
晴,初三,年已过
既然直播如此影响情绪,为什么还要直播?因为无聊?明明那么多事情可以打发时间。 真不想懂。 今日初三,昨天晚上小舅家聚,今天大舅家聚,计划明天小姨妈家聚。 今晚喝了点大舅哥哥泡的白葡萄酒,…...
Vue3 v-bind 和 v-model 对比
1. 基本概念 1.1 v-bind 单向数据绑定从父组件向子组件传递数据简写形式为 : 1.2 v-model 双向数据绑定父子组件数据同步本质是 v-bind 和 v-on 的语法糖 2. 基础用法对比 2.1 表单元素绑定 <!-- v-bind 示例 --> <template><input :value"text&quo…...
Smalltalk语言是何物?面向对象鼻祖Simula的诞生?Simula和Smalltalk有什么区别?面向对象设计?
Smalltalk语言是何物? Smalltalk语言的前身可以追溯到Flex系统,这是由Alan Kay最早提出的。在随后的发展中,Smalltalk逐渐演化,并出现了Smalltalk-72和Smalltalk-76等版本。最终,在经过近10年的研究与发展后,Xerox研究…...
KVM/ARM——基于ARM虚拟化扩展的VMM
1. 前言 ARM架构为了支持虚拟化做了些扩展,称为虚拟化扩展(Virtualization Extensions)。原先为VT-x创建的KVM(Linux-based Kernel Virtual Machine)适配了ARM体系结构,引入了KVM/ARM (the Linux ARM hypervisor)。KVM/ARM没有在hypervisor中引入复杂的…...
Windows系统中Docker可视化工具对比分析,Docker Desktop,Portainer,Rancher
Docker可视化工具对比分析,Docker Desktop,Portainer,Rancher Windows系统中Docker可视化工具对比分析1. 工具概览2. Docker Desktop官网链接:主要优点:主要缺点:版本更新频率: 3. Portainer官网…...
【架构面试】二、消息队列和MySQL和Redis
MQ MQ消息中间件 问题引出与MQ作用 常见面试问题:面试官常针对项目中使用MQ技术的候选人提问,如如何确保消息不丢失,该问题可考察候选人技术能力。MQ应用场景及作用:以京东系统下单扣减京豆为例,MQ用于交易服和京豆服…...
算法【完全背包】
完全背包与01背包的区别仅在于每种商品可以选取无限次。时间复杂度O(物品数量 * 背包容量) 下面通过题目加深理解。 题目一 测试链接:疯狂的采药 - 洛谷 分析:这是一道完全背包的模板题。对于第i个物品的可能性展开也有两种,第一种是不取第…...
二叉树的遍历
有一个结点的二叉树。给出每个结点的两个子结点编号,建立一棵二叉树,如果是叶子结点,则输入 0 0。 建好树这棵二叉树之后,依次求出它的前序、中序、后序列遍历。 输入格式: 第一行一个整数n ,表示结点数。 之后n 行…...
1.31 实现五个线程的同步
1.使用互斥锁实现 1>程序代码 #include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <pthread.h> #include &l…...
three.js+WebGL踩坑经验合集(6.1):负缩放,负定矩阵和行列式的关系(2D版本)
春节忙完一轮,总算可以继续来写博客了。希望在春节假期结束之前能多更新几篇。 这一篇会偏理论多一点。笔者本没打算在这一系列里面重点讲理论,所以像相机矩阵推导这种网上已经很多优质文章的内容,笔者就一笔带过。 然而关于负缩放…...
【开源免费】基于SpringBoot+Vue.JS体育馆管理系统(JAVA毕业设计)
本文项目编号 T 165 ,文末自助获取源码 \color{red}{T165,文末自助获取源码} T165,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...
《大数据时代“快刀”:Flink实时数据处理框架优势全解析》
在数字化浪潮中,数据呈爆发式增长,实时数据处理的重要性愈发凸显。从金融交易的实时风险监控,到电商平台的用户行为分析,各行业都急需能快速处理海量数据的工具。Flink作为一款开源的分布式流处理框架,在这一领域崭露头…...
antdesignvue统计数据源条数、计算某列合计值、小数计算不精确多了很多小数位
1.在</a-table>下方加如下代码 <div>数据总条数:{ {tableData.length}}       <template>A列合计:{ {sum}}</template> </div> 注:tableData为<a-tabl…...
02.05、链表求和
02.05、[中等] 链表求和 1、题目描述 给定两个用链表表示的整数,每个节点包含一个数位。 这些数位是反向存放的,也就是个位排在链表首部。 编写函数对这两个整数求和,并用链表形式返回结果。 2、解题思路 本题要求对两个链表表示的整数…...
dmfldr实战
dmfldr实战 本文使用达梦的快速装载工具,对测试表进行数据导入导出。 新建测试表 create table “BENCHMARK”.“TEST_FLDR” ( “uid” INTEGER identity(1, 1) not null , “name” VARCHAR(24), “begin_date” TIMESTAMP(0), “amount” DECIMAL(6, 2), prim…...
Kafka 副本机制(包含AR、ISR、OSR、HW 和 LEO 介绍)
文章目录 Kafka 副本机制(包含AR、ISR、OSR、HW 和 LEO 介绍)1. 副本的基本概念2. 副本同步和一致性2.1 AR(Assigned Replicas)2.2 ISR(In-Sync Replicas)2.3 OSR(Out-of-Sync Replicas…...
爬虫基础(二)Web网页的基本原理
一、网页的组成 网页由三部分构成:HTML、JavaScript、CSS。 (1)HTML HTML 相当于网页的骨架,它通过使用标签来定义网页内容的结构。 举个例子: 它把图片标签为img、把视频标签为video,然后组合到一个界面…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
[USACO23FEB] Bakery S
题目描述 Bessie 开了一家面包店! 在她的面包店里,Bessie 有一个烤箱,可以在 t C t_C tC 的时间内生产一块饼干或在 t M t_M tM 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC,tM≤109)。由于空间…...
