当前位置: 首页 > 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;点击左上角的首页。在首页栏中&#…...

2026年,本地精准营销高性价比服务商来袭,你还不了解一下?

在本地商业竞争日益激烈的2026年&#xff0c;实体店面临着诸多挑战&#xff0c;引流难、成本高、复购率低等问题困扰着众多商家。而中粤&#xff08;广州&#xff09;信息科技有限公司作为本地精准营销的高性价比服务商&#xff0c;正以其独特的优势和卓越的服务&#xff0c;为…...

【深度解析】AI Coding 模型竞速:从 Claude Mythos 安全编码到 GPT-5.6 传闻,如何落地代码审查智能体

摘要 AI 编码模型正在从“代码补全”进入“复杂代码库理解、漏洞发现与自动修复”阶段。本文结合 Claude Mythos、Claude Opus 4.8 与 GPT-5.6 相关信息&#xff0c;解析新一代 Coding Agent 的技术趋势&#xff0c;并给出基于大模型 API 的代码安全审查实战方案。背景介绍&…...

LizzieYzy:你的智能围棋教练,让AI分析变得简单有趣 [特殊字符]

LizzieYzy&#xff1a;你的智能围棋教练&#xff0c;让AI分析变得简单有趣 &#x1f3af; 【免费下载链接】lizzieyzy LizzieYzy - GUI for Game of Go 项目地址: https://gitcode.com/gh_mirrors/li/lizzieyzy 还在为复盘找不到关键点而烦恼吗&#xff1f;想提升棋力却…...

如何用HsMod解锁炉石传说60+项隐藏功能:终极优化指南

如何用HsMod解锁炉石传说60项隐藏功能&#xff1a;终极优化指南 【免费下载链接】HsMod Hearthstone Modification Based on BepInEx 项目地址: https://gitcode.com/GitHub_Trending/hs/HsMod HsMod是一款基于BepInEx开发的炉石传说功能增强插件&#xff0c;为玩家提供…...

3分钟告别英文恐惧:Android Studio中文界面轻松切换指南

3分钟告别英文恐惧&#xff1a;Android Studio中文界面轻松切换指南 【免费下载链接】AndroidStudioChineseLanguagePack AndroidStudio中文插件(官方修改版本&#xff09; 项目地址: https://gitcode.com/gh_mirrors/an/AndroidStudioChineseLanguagePack 你是否曾经因…...

Lovable电商网站搭建:如何用不到3人技术团队,72小时内上线PCI-DSS合规MVP版本?

更多请点击&#xff1a; https://codechina.net 第一章&#xff1a;Lovable电商网站搭建 Lovable 是一个面向中小商户的轻量级电商解决方案&#xff0c;采用现代 Web 技术栈构建&#xff0c;强调可扩展性、用户体验与快速部署能力。本章将指导你从零开始搭建一个具备商品展示、…...

深度解析:JetBrains IDE试用期重置机制的技术实现

深度解析&#xff1a;JetBrains IDE试用期重置机制的技术实现 【免费下载链接】ide-eval-resetter 项目地址: https://gitcode.com/gh_mirrors/id/ide-eval-resetter 在软件开发工作流中&#xff0c;JetBrains IDE试用期管理是一个常见的技术挑战&#xff0c;尤其是在多…...

Burp抓包失败的五大隐形墙与HTTPS解密断裂点排查指南

1. 这不是Burp用得不对&#xff0c;是环境链路断在了你没看见的地方“Burp抓不到包”——这句话我过去三年里听开发、测试、刚转安全的新人说了不下两百遍。但真正打开Burp一看&#xff0c;Proxy标签页里空空如也&#xff0c;连个localhost:8080的请求都没有&#xff0c;十有八…...

CentOS 8/Stream 8系统DNF换源后,安装软件还是慢?试试这几个排查命令和优化技巧

CentOS 8/Stream 8系统DNF换源后安装缓慢的深度排查与优化指南当你已经按照教程将CentOS 8/Stream 8的DNF源切换为国内镜像&#xff0c;却发现软件安装速度依然不尽如人意时&#xff0c;这种体验确实令人沮丧。作为长期使用CentOS系统的技术专家&#xff0c;我完全理解这种&quo…...

手机也能玩转无人机仿真:用安卓QGC App连接同一WiFi下的PX4 JMAVSim模拟器

手机也能玩转无人机仿真&#xff1a;用安卓QGC App连接同一WiFi下的PX4 JMAVSim模拟器 无人机开发者和爱好者们&#xff0c;是否曾想过用手机就能完成整个无人机仿真测试流程&#xff1f;告别笨重的电脑束缚&#xff0c;只需一部安卓设备&#xff0c;就能在沙发上调试飞控算法。…...