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

★【二叉搜索树(中序遍历特性)】【 ★递归+双指针】Leetcode 98. 验证二叉搜索树

★【二叉搜索树(中序遍历特性)】【 ★递归+双指针】Leetcode 98. 验证二叉搜索树

    • 二叉搜索树
  • 98. 验证二叉搜索树
    • 解法1 笨 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以
    • ★解法2 不使用数组 递归法

---------------🎈🎈题目链接🎈🎈-------------------

二叉搜索树

二叉搜索树


98. 验证二叉搜索树

在这里插入图片描述


解法1 笨 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以

二叉搜索树的特性:中序遍历是单调递增的

时间复杂度:
中序遍历二叉搜索树的时间复杂度为 O(n),其中 n 是二叉树中节点的数量。
检查列表是否按升序排列的时间复杂度为 O(n)。
因此,总的时间复杂度为 O(n)。

空间复杂度:
存储节点值的列表的空间复杂度为 O(n),因为需要存储整个树的节点值。
递归调用时的栈空间复杂度取决于树的高度,最坏情况下为 O(n),平均情况下为 O(log n),其中 n 是树中的节点数量。
因此,总的空间复杂度为 O(n)。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isValidBST(TreeNode root) {// 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以List<Integer> mylist = new ArrayList<>();helper(root,mylist);for(int i = 0; i < mylist.size(); i++){if(i>0 && (long)mylist.get(i)-(long)mylist.get(i-1) <= 0){return false;}}return true;}public void helper(TreeNode root,List<Integer> mylist){if(root == null) return ;helper(root.left,mylist);mylist.add(root.val);helper(root.right,mylist);}
}

★解法2 不使用数组 递归法

另一个题也是这样 530. 二叉搜索树的最小绝对差


class Solution {TreeNode pre = null;  public boolean isValidBST(TreeNode root) {// 不用数组直接用二叉树结构进行判断if(root == null) return true;  // 终止条件// 中序遍历顺序 当前的和前一个进行比较boolean left = isValidBST(root.left); // 左if(pre!= null && root.val <= pre.val){ // 中return false;}pre = root;boolean right = isValidBST(root.right); //右if(left && right) return true;else return false;}
}

相关文章:

★【二叉搜索树(中序遍历特性)】【 ★递归+双指针】Leetcode 98. 验证二叉搜索树

★【二叉搜索树&#xff08;中序遍历特性&#xff09;】【 ★递归双指针】Leetcode 98. 验证二叉搜索树 二叉搜索树 98. 验证二叉搜索树解法1 笨 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以★解法2 不使用数组 递归法 ---------------&#x1f388;&#x1f38…...

打造无缝滚动体验:JavaScript中的scrollIntoView()方法实战指南

在现代Web开发中&#xff0c;提升用户体验是至关重要的。通过JavaScript的scrollIntoView()方法&#xff0c;我们可以为用户创造出流畅而令人愉悦的滚动体验。本文将深入研究scrollIntoView()的强大功能&#xff0c;并结合实例演示如何在项目中巧妙应用&#xff0c;以打造出无缝…...

实战:如何将Oracle单实例数据库转换成Oracle RAC数据库

导读 本文介绍如何将Oracle单实例数据库转换成Oracle RAC数据库 环境说明&#xff1a; 数据库节点2上有个单实例数据库zlxdb2&#xff0c;现在要将zlxdb2转换成RAC数据库&#xff0c;RAC数据库的两个实例分别是lzydb1和lzydb2。 以下是详细的操作步骤&#xff1a; 1、查看zlxdb…...

基于华为atlas的分类模型实战

分类模型选用基于imagenet训练的MobileNetV3模型&#xff0c;分类类别为1000类。 pytorch模型导出为onnx&#xff1a; 修改mobilenetv3.py中网络结构&#xff0c;模型选用MobileNetV3_Small模型&#xff0c;网络输出节点增加softmax层&#xff0c;将原始的return self.linear4…...

编程语言:SQL Server数据库使用教程,SQL Server增删改查语句

「作者主页」&#xff1a;士别三日wyx 「作者简介」&#xff1a;CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」&#xff1a;对网络安全感兴趣的小伙伴可以关注专栏《网络安全自学教程》 SQL Server是微软提供的一种关系型数据库&#xff0c…...

【tableau学习笔记】tableau无法连接数据源

【tableau学习笔记】tableau无法连接数据源 背景&#xff1a; 学校讲到Tableau&#xff0c;兴奋下载Kaggle Excel&#xff0c;一看后缀CSV&#xff0c;导入Tableau发现报错“tableau无法连接数据源”&#xff0c;自作聪明改为后缀XLSX&#xff0c;bug依旧。 省流&#xff1a…...

cetos7 Docker 安装 gitlab

一、gitlab 简单介绍和安装要求 官方文档&#xff1a;https://docs.gitlab.cn/jh/install/docker.html 1.1、gitlab 介绍 gitLab 是一个用于代码仓库管理系统的开源项目&#xff0c;使用git作为代码管理工具&#xff0c;并在此基础上搭建起来的Web服务平台&#xff0c;通过该平…...

无极低码:无极低码部署版操作指南

无极低码 &#xff1a;https://wheart.cn 无极低码是一个面向开发者的工具&#xff0c;旨在为开发者、创业者或研发企业&#xff0c;提供快速&#xff0c;高效&#xff0c;标准化&#xff0c;可定制&#xff0c;私有化部署的平台&#xff0c;在兼顾开发速度的同时&#xff0c;兼…...

C语言实现日本某地发生了一件谋杀案

题目 猜凶手 题目内容&#xff1a; 日本某地发生了一件谋杀案&#xff0c;警察通过排查确定杀人凶手必为4个嫌疑犯的一个。 以下为4个嫌疑犯的供词: A说&#xff1a;不是我。 B说&#xff1a;是C。 C说&#xff1a;是D。 D说&#xff1a;C在胡说 已知3个人说了真话&…...

【C++】const成员

个人主页 &#xff1a; zxctscl 如有转载请先通知 文章目录 1. 前言2. const成员3. 取地址及const取地址操作符重载 1. 前言 在之前已经已经分享过了关于 【C】类和对象之常引用与运算符重载&#xff0c;这次分享的有关const的内容&#xff0c;话不多说&#xff0c;正文开始。…...

利用小蜜蜂AI智能问答ChatGPT+AI高清绘图生成图文故事案例

利用小蜜蜂AI智能问答ChatGPTAI高清绘图生成图文故事案例 这段时间利用小蜜蜂AI网站做了一些编程、绘图以及数据分析方面的案例。再过几个月&#xff0c;我的大孙子就要出生了。我要用小蜜蜂AI智能问答和AI高清绘图为大孙子生成一个1-9的数字图文故事。 小蜜蜂AI网站可以扫如…...

Github项目推荐-LightMirrors

项目地址 https://github.com/NoCLin/LightMirrors 项目简述 “LightMirrors是一个开源的缓存镜像站服务&#xff0c;用于加速软件包下载和镜像拉取。目前支持DockerHub、PyPI、PyTorch、NPM等镜像缓存服务。 当前项目仍处于早期阶段。”–来自项目说明。 也就是说&#xff…...

day14:栈排序

问题描述&#xff1a; 栈排序。 编写程序&#xff0c;对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据&#xff0c;但不得将元素复制到别的数据结构&#xff08;如数组&#xff09;中。该栈支持如下操作&#xff1a;push、pop、peek 和 isEmpty。当栈…...

【LeetCode:2368. 受限条件下可到达节点的数目 + BFS】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…...

pyorbbecsdk奥比中光python版本SDK在Windows下环境配置笔记

1、概述 Orbbec SDK Python Wrapper基于Orbbec SDK进行设计封装&#xff0c;主要实现数据流接收&#xff0c;设备指令控制。 2、系统要求 2.1、操作系统 Windows&#xff1a;Windows 10 (x64)&#xff08;本文 针对windows&#xff09;Linux: 18.04/20.04/22.04 (x64)Arm32:…...

YOLOV8介绍

原文链接&#xff1a; 1、 详解YOLOv8网络结构/环境搭建/数据集获取/训练/推理/验证/导出 2、Yolov8的详解与实战 3、YOLOV8模型训练部署&#xff08;实战&#xff09;&#xff08;&#xff09;有具体部署和训练实现代码YOLOV8模型训练部署&#xff08;实战&#xff09;&…...

【ElfBoard】基于 Linux 的智能家居小项目

大家好&#xff0c;我是 Hello阿尔法&#xff0c;这段时间参与了保定飞凌嵌入式技术有限公司举办的 ElfBoard 共创社招募活动&#xff0c;并有幸成为了一名共创官&#xff0c;官方寄来了一块 ELF 1 开发板&#xff0c;开箱看这里 ELF 1 开箱初体验。 作为共创官&#xff0c;我…...

自动化测试介绍、selenium用法(自动化测试框架+爬虫可用)

文章目录 一、自动化测试1、什么是自动化测试&#xff1f;2、手工测试 vs 自动化测试3、自动化测试常见误区4、自动化测试的优劣5、自动化测试分层6、什么项目适合自动化测试 二、Selenuim1、小例子2、用法3、页面操作获取输入内容模拟点击清空文本元素拖拽frame切换窗口切换/标…...

深度学习的一个完整过程通常包括以下几个步骤

深度学习的一个完整过程通常包括以下几个步骤&#xff1a; 问题定义和数据收集&#xff1a; 定义清晰的问题&#xff0c;明确任务的类型&#xff08;分类、回归、聚类等&#xff09;以及预期的输出。收集和整理用于训练和评估模型的数据集。确保数据集的质量&#xff0c;进行预…...

WPS如何共享文件和文件夹

1 WPS共享单个文件 用WPS打开要分享的文件&#xff0c;点击右上角的“分享”键&#xff0c;选择上传到云端。 之后点击“创建并分享”&#xff0c;即可分享该文档。 2 WPS创建共享文件夹 2.1 如何共享文件夹 首先打开WPS&#xff0c;点击左上角的首页。在首页栏中&#…...

ESP32多任务水位监测:从Arduino到ESP-IDF的FreeRTOS实战

1. 项目概述&#xff1a;从Arduino到ESP-IDF的跃迁去年我在做毕业设计时&#xff0c;为了搭建一个ESP32的传感器节点演示程序&#xff0c;第一次深入使用了FreeRTOS。那段时间&#xff0c;我几乎天天和任务调度、队列、信号量打交道&#xff0c;从最初的一头雾水到后来能流畅地…...

长期使用Token Plan套餐在项目开发中的成本观察

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 长期使用Token Plan套餐在项目开发中的成本观察 在AI驱动的项目开发中&#xff0c;成本控制与预算管理是团队负责人必须面对的现实…...

破解材料数据荒:合成数据与随机森林预测聚合物阻燃性能

1. 项目概述与核心挑战在材料研发领域&#xff0c;尤其是涉及公共安全的聚合物阻燃性研究&#xff0c;传统实验方法正面临巨大瓶颈。想象一下&#xff0c;你是一位材料工程师&#xff0c;需要设计一种用于高铁内饰或高层建筑电缆护套的新型聚合物&#xff0c;其阻燃性能必须满足…...

HoRain云--CLAUDE.md 使用指南

&#x1f3ac; HoRain云小助手&#xff1a;个人主页 &#x1f525; 个人专栏: 《Linux 系列教程》《c语言教程》 ⛺️生活的理想&#xff0c;就是为了理想的生活! ⛳️ 推荐 前些天发现了一个超棒的服务器购买网站&#xff0c;性价比超高&#xff0c;大内存超划算&#xff01;…...

基于STM32与LoRa的低功耗物联网气象站DIY全攻略

1. 项目概述&#xff1a;打造一个低功耗的家庭气象站前阵子想给家里的智能家居系统加点“环境感知”能力&#xff0c;琢磨着搞个能实时监测室外温湿度、风速风向的小玩意儿。市面上成品气象站要么数据出不来&#xff0c;要么功耗感人&#xff0c;不适合长期户外部署。于是&…...

量子机器学习与傅里叶分析:革新期权定价的混合计算范式

1. 项目概述&#xff1a;当量子机器学习遇见金融定价在金融工程的核心地带&#xff0c;期权定价一直是个计算密集型的硬骨头。传统的蒙特卡洛模拟虽然通用&#xff0c;但为了达到足够的精度&#xff0c;动辄需要百万甚至千万次的路径模拟&#xff0c;计算成本高昂。近年来&…...

大模型测试新范式:Claude端到端验证的5层断言体系(语义一致性/上下文连贯性/安全边界/成本阈值/时序鲁棒性)

更多请点击&#xff1a; https://codechina.net 第一章&#xff1a;大模型测试新范式&#xff1a;Claude端到端验证的5层断言体系&#xff08;语义一致性/上下文连贯性/安全边界/成本阈值/时序鲁棒性&#xff09; 传统LLM测试常聚焦于准确率或BLEU等静态指标&#xff0c;而Cla…...

鼎讯AM-601光纤熔接机:交通通信建设与维护的可靠伙伴

在铁路、高速公路等交通基础设施的智能化建设中&#xff0c;稳定高效的光纤网络是指挥调度、安全监控等核心系统运行的生命线。鼎讯AM-601光纤熔接机&#xff0c;作为一款专为严苛环境设计的六马达便携式熔接设备&#xff0c;正成为保障这些关键通信链路畅通无阻的可靠选择。无…...

8大网盘文件直链一键获取:LinkSwift让你的下载速度突破限速瓶颈

8大网盘文件直链一键获取&#xff1a;LinkSwift让你的下载速度突破限速瓶颈 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移动云…...

如何高效实现前端文件下载:FileSaver.js完整实用指南

如何高效实现前端文件下载&#xff1a;FileSaver.js完整实用指南 【免费下载链接】FileSaver.js An HTML5 saveAs() FileSaver implementation 项目地址: https://gitcode.com/gh_mirrors/fi/FileSaver.js FileSaver.js是一款轻量级的HTML5文件保存解决方案&#xff0c;…...