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

43 验证二叉搜索树

验证二叉搜索树

    • 理解题意:验证搜索二叉树:中序遍历是升序
    • 题解1 递归(学习学习!)
    • 题解2 中序遍历(保持升序)

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

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

  • 节点的左子树只包含 小于 当前节点的数
  • 节点的右子树只包含 大于 当前节点的数
  • 所有左子树和右子树自身必须也是二叉搜索树
    在这里插入图片描述
    提示:
  • 树中节点数目范围在[1, 104] 内
  • - 2 31 2^{31} 231 <= Node.val <= 2 31 − 1 2^{31} - 1 2311

理解题意:验证搜索二叉树:中序遍历是升序

题解1 递归(学习学习!)

/*** 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 check(TreeNode* root, long low, long high){if(! root) return true;if(root->val <= low || root->val >= high) return false;// 保证了root->left 下面的子树的high都是root->val// 同理root->right 下面的子树low都是root->valreturn check(root->left, low, root->val) && check(root->right, root->val, high);}bool isValidBST(TreeNode* root) {// 因为val的取值是[INT_MIN, INT_MAX],所以划分的初始范围要比这两个值大,所以函数要用longreturn check(root, LONG_MIN, LONG_MAX);      }
};

在这里插入图片描述

题解2 中序遍历(保持升序)

class Solution {
public:bool isValidBST(TreeNode* root) {if(! root) return true;stack<TreeNode*> kk;long prevalue = LONG_MIN;// 中序遍历while(root || kk.size()){while(root){kk.push(root);root = root->left;}root = kk.top();kk.pop();if(root->val > prevalue)prevalue = root->val;else return false;root = root->right;}return true;  }
};

在这里插入图片描述

相关文章:

43 验证二叉搜索树

验证二叉搜索树 理解题意&#xff1a;验证搜索二叉树&#xff1a;中序遍历是升序题解1 递归&#xff08;学习学习&#xff01;&#xff09;题解2 中序遍历&#xff08;保持升序&#xff09; 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个 有效的二叉搜索树。 有…...

深度学习笔记之微积分及绘图

深度学习笔记之微积分及绘图 学习资料来源&#xff1a;微积分 %matplotlib inline from matplotlib_inline import backend_inline from mxnet import np, npx from d2l import mxnet as d2lnpx.set_np()def f(x):return 3 * x ** 2 - 4 * xdef numerical_lim(f, x, h):retur…...

java Spring Boot按日期 限制大小分文件记录日志

上文 java Spring Boot 将日志写入文件中记录 中 我们实现另一个将控制台日志写入到 项目本地文件的效果 但是 这里有个问题 比如 我项目是个大体量的企业项目 每天会有一百万用户访问 那我每天的日志都记载同一个文件上 那不跟没记没什么区别吗&#xff1f; 东西怎么找&#x…...

CSS 语法

CSS 实例 CSS 规则由两个主要的部分构成&#xff1a;选择器&#xff0c;以及一条或多条声明: 选择器通常是您需要改变样式的 HTML 元素。 每条声明由一个属性和一个值组成。 属性&#xff08;property&#xff09;是您希望设置的样式属性&#xff08;style attribute&#x…...

Vue3+TS+ECharts5实现中国地图数据信息显示

1.引言 最近在做一个管理系统&#xff0c;主要技术栈使用的是Vue3TSViteElementPlus&#xff0c;主要参考项目是yudao-ui-admin-vue3&#xff0c;其中用到ECharts5做数字大屏&#xff0c;展示中国地图相关信息&#xff0c;以此基础做一个分享&#xff0c;写下这篇文章。 &quo…...

PowerShell 内网不能直接安装SqlServer模块的处理办法

PowerShell 内网不能直接安装SqlServer模块的处理办法 文章目录 下载sqlserver module安装sqlserver module导入和验证sqlserver 模块推荐阅读 下载sqlserver module 首先先将sqlserver.nupkg下载到本地&#xff0c;我是放到了C:\windows\system32目录下。 PowerShell Galler…...

Git使用【下】

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;那个传说中的man的主页 &#x1f3e0;个人专栏&#xff1a;题目解析 &#x1f30e;推荐文章&#xff1a;题目大解析&#xff08;3&#xff09; 目录 &#x1f449;&#x1f3fb;标签管理理解标签标签运用 …...

自然语言处理的分类

动动发财的小手&#xff0c;点个赞吧&#xff01; 简介 作为理解、生成和处理自然语言文本的有效方法&#xff0c;自然语言处理&#xff08;NLP&#xff09;的研究近年来呈现出快速传播和广泛采用。鉴于 NLP 的快速发展&#xff0c;获得该领域的概述并对其进行维护是很困难的。…...

Flutter笔记:手写并发布一个人机滑动验证码插件

Flutter笔记 手写一个人机滑块验证码 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/133529459 写 Flut…...

RabbitMQ安装与简单使用

安装 下载资源 可以访问官网查看下载信息rabbitmq官网 选择合适的版本&#xff0c;注意&#xff1a;rabbitmq需要下载一个Erlang才能使用 我自己是在一下两个连接中下载的 rabbitmq 3.8.8 erlang 21.3.8.15 需要下载其他版本的同学注意erlang版本是否匹配&#xff0c;可以访…...

不做静态化,当部署到服务器上的项目刷新出现404【已解决】

当线上项目刷新出现404页面解决方法&#xff1a; 在nginx配置里加入这样一段代码 try_files $uri $uri/ /index.html; 它的作用是尝试按照给定的顺序访问文件 变量解释 try_files 固定语法 $uri 指代home文件(ip地址后面的路径&#xff0c;假如是127.0.0.1/index/a.png&…...

SpringBoot结合Redisson实现分布式锁

&#x1f9d1;‍&#x1f4bb;作者名称&#xff1a;DaenCode &#x1f3a4;作者简介&#xff1a;啥技术都喜欢捣鼓捣鼓&#xff0c;喜欢分享技术、经验、生活。 &#x1f60e;人生感悟&#xff1a;尝尽人生百味&#xff0c;方知世间冷暖。 &#x1f4d6;所属专栏&#xff1a;Sp…...

css字体属性

一、CSS字体属性用于设置文本的字体样式。以下是常用的CSS字体属性&#xff1a; font-family&#xff1a;设置文本的字体系列&#xff0c;可以使用多个字体&#xff0c;用逗号分隔。font-size&#xff1a;设置文本的字体大小&#xff0c;可用像素、百分比、em等单位。font-wei…...

云原生微服务治理 第四章 Spring Cloud Netflix 服务注册/发现组件Eureka

系列文章目录 第一章 Java线程池技术应用 第二章 CountDownLatch和Semaphone的应用 第三章 Spring Cloud 简介 第四章 Spring Cloud Netflix 之 Eureka 文章目录 系列文章目录[TOC](文章目录) 前言1、Eureka 两大组件2、Eureka 服务注册与发现3、案例3.1、创建主工程3.1.1、主…...

【白细胞介素6(IL-6)】

## IL-6&#xff0c;至关重要的多功能细胞因子 ## 聊一聊白细胞介素6&#xff08;IL-6&#xff09; ## 简述&#xff1a;国内外IL-6 _ IL-6R在研药物一览_药智新闻.2017 ## 研究项目&#xff5c;靶向IL-6药物在研现状 2021...

设计模式之抽象工厂模式--创建一系列相关对象的艺术(简单工厂、工厂方法、到抽象工厂的进化过程,类图NS图)

目录 概述概念适用场景结构类图 衍化过程业务需求基本的数据访问程序工厂方法实现数据访问程序抽象工厂实现数据访问程序简单工厂改进抽象工厂使用反射抽象工厂反射配置文件衍化过程总结 常见问题总结 概述 概念 抽象工厂模式是一种创建型设计模式&#xff0c;它提供了一种将相…...

大数据-玩转数据-Flink SQL编程实战 (热门商品TOP N)

一、需求描述 每隔30min 统计最近 1hour的热门商品 top3, 并把统计的结果写入到mysql中。 二、需求分析 1.统计每个商品的点击量, 开窗2.分组窗口分组3.over窗口 三、需求实现 3.1、创建数据源示例 input/UserBehavior.csv 543462,1715,1464116,pv,1511658000 662867,22…...

python中实现定时任务的几种方案

目录 while True: sleep()Timeloop库threading.Timersched模块schedule模块APScheduler框架Celery框架数据流工具Apache Airflow概述Airflow 核心概念Airflow 的架构 总结以下几种方案实现定时任务&#xff0c;可根据不同需求去使用不同方案。 while True: sleep() 利用whil…...

AcWing算法提高课-5.6.1同余方程

宣传一下 算法提高课整理 CSDN个人主页&#xff1a;更好的阅读体验 原题链接 题目描述 求关于 x x x 的同余方程 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 的最小正整数解。 输入格式 输入只有一行&#xff0c;包含两个正整数 a , b a,b a,b&#xff0c;用一…...

Docker Tutorial

什么是Docker 为每个应用提供完全隔离的运行环境 Dockerfile&#xff0c; Image&#xff0c;Container Image&#xff1a; 相当于虚拟机的快照&#xff08;snapshot&#xff09;里面包含了我们需要部署的应用程序以及替它所关联的所有库。通过image&#xff0c;我们可以创建很…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...