【力扣题解】P98-验证二叉搜索树-Java题解

花无缺

👨‍💻博客主页:@花无缺
欢迎 点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏 【力扣题解】


文章目录

  • 【力扣题解】P98-验证二叉搜索树-Java题解
    • 🌏题目描述
    • 💡题解
    • 🌏总结


【力扣题解】P98-验证二叉搜索树-Java题解

P98.验证二叉搜索树

🌏题目描述

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

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

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

在这里插入图片描述

输入:root = [2,1,3]
输出:true

示例 2:

在这里插入图片描述

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

提示:

  • 树中节点数目范围在[1, 104]
  • -231 <= Node.val <= 231 - 1

💡题解

递归法1

// list 保存中序序列
List<Long> list = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
    // 中序遍历二叉树, 将中序序列保存到 list 中
    dfs(root);
    // 遍历 list, 如果 list 是一个递增的序列, 那么这就是一棵二叉搜索树
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.get(i) >= list.get(i + 1)) {
            return false;
        }
    }
    return true;
}
public void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    // 中序遍历, 将节点值放入 list
    list.add((long) root.val);
    dfs(root.right);
}

递归法2

// pre 保存上一个遍历的节点值
long pre = Long.MIN_VALUE;
public boolean isValidBST2(TreeNode root) {
    // 空树也是二叉搜索树
    if (root == null) {
        return true;
    }
    // 递归判断左子树
    boolean left = isValidBST2(root.left);
    // 如果当前节点的值大于上一个遍历的节点值那么就是符合二叉搜索树的
    // 继续遍历
    if (root.val > pre) {
        pre = root.val;
    //     如果当前节点的值小于等于上一个遍历的节点值, 那么该树就不是二叉搜索树
    } else {
        return false;
    }
    // 递归判断右子树
    boolean right = isValidBST2(root.right);
    // 左右子树都是二叉搜索树
    return left && right;
}

时间复杂度均为O(n),需要遍历二叉树的所有节点,二叉树节点数为 n。

🌏总结

我们知道二叉搜索树的左子树的所有节点值一定小于根节点,右子树的所有节点值一定大于根节点,并且所有子树都是二叉搜索树,根据二叉树的这个特性,我们可以推出,二叉搜索树的中序序列一定是一个由小到大排列的递增序列,所以我们可以对树进行中序遍历,然后判断这个序列是否是严格递增的,如果是那么就是二叉搜索树,如果不是那么就不是二叉搜索树。

递归1解法就是采用这个思路的,将中序遍历序列放入列表 list 中,然后判断 list 是否递增。而递归2解法可以不使用列表,而是直接在递归的时候判断当前节点是否大于上一个遍历过的节点,如果递归结束所有节点都满足那么就是二叉搜索树,只要有一个节点是小于等于上一个节点的,那么就不是二叉搜索树。另外,要注意 pre 的初始值要比 int 的最小值小,因为题目的节点值数据范围是整个 int 范围,所以我们直接将 pre 设置为 long 类型数据,并初始化为 long 的最小值。

作者:花无缺(huawuque404.com)


🌸欢迎关注我的博客:花无缺-每一个不曾起舞的日子都是对生命的辜负~
🍻一起进步-刷题专栏:【力扣题解】
🥇往期精彩好文:
📢【全网最全爱心代码仓库】
📢【CSS选择器全解指南】
📢【HTML万字详解】
你们的点赞👍 收藏⭐ 留言📝 关注✅
是我持续创作,输出优质内容的最大动力!
谢谢!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/283395.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

分割数组的最大差值 - 华为OD统一考试

分割数组的最大差值 - 华为OD统一考试 OD统一考试 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C 题目描述 给定一个由若干整数组成的数组nums &#xff0c;可以在数组内的任意位置进行分割&#xff0c;将该数组分割成两个非空子数组(即左数组和右数组)&#xf…

【2024最新版】neo4j安装配置

neo4j安装 写在最前面下载配置环境&#xff08;还是不行&#xff1f;&#xff09;启动neo4jpython中调用 写在最前面 之前我安装过&#xff0c;还写了一篇笔记 结果意外发现没有了&#xff0c;而且和之前安装的步骤不一样了&#xff0c;因此再次记录安装过程 下载 https://ne…

OpenGL FXAA抗锯齿算法(Qt)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 之前已经提供了使用VCG读取Mesh的方式,接下来就需要针对读取的网格数据进行一些渲染操作了。在绘制Mesh数据时总会遇到图形的抗锯齿问题,OpenGL本身已经为我们提供了一种MSAA技术,但该技术对于一些实时渲染性能有…

【数据结构】栈和队列(栈的基本操作和基础知识)

&#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm1001.2014.3001.5482 目录 前言 栈 栈的概念和结构 栈的实现 ​…

Rust使用gRPC

需要先安装protoc&#xff08;Protocol Buffers Compiler&#xff09;&#xff0c;可据此Protobuf Compiler Installation下载 第一步&#xff1a;创建项目 创建两个新的Rust项目&#xff0c;分别作为服务端与客户端&#xff1a; cargo new rust_grpc_servercargo new rust_grp…

elasticsearch系列九:异地容灾-CCR跨集群复制

概述 起初只在部分业务中采用es存储数据&#xff0c;在主中心搭建了个集群&#xff0c;随着es在我们系统中的地位越来越重要&#xff0c;数据也越来越多&#xff0c;针对它的安全性问题也越发重要&#xff0c;那如何对es做异地容灾呢&#xff1f; 今天咱们就一起看下官方提供的…

Redis(上)

1、redis Redis是一个完全开源免费的高性能&#xff08;NOSQL&#xff09;的key-value数据库。它遵守BSD协议&#xff0c;使用ANSI C语言编写&#xff0c;并支持网络和持久化。Redis拥有极高的性能&#xff0c;每秒可以进行11万次的读取操作和8.1万次的写入操作。它支持丰富的数…

步进电机为什么叫步进电机,内部结构是什么,工作原理是什么,有什么特点,什么用途。

问题描述&#xff1a;步进电机为什么叫步进电机&#xff0c;内部结构是什么&#xff0c;工作原理是什么&#xff0c;有什么特点&#xff0c;什么用途。 问题解答&#xff1a; "步进"一词表示电机按照固定的步进角度运动。步进电机以控制脉冲信号来驱动转子按照一定的…

Vue2中使用echarts,并从后端获取数据同步

一、安装echarts npm install echarts -S 二、导入echarts 在script中导入&#xff0c;比如&#xff1a; import * as echarts from "echarts"; 三、查找要用的示例 比如柱状图 四、初始化并挂载 <template><div id"total-orders-chart" s…

三天吃透Java基础面试八股文

给大家分享我整理的Java高频面试题&#xff0c;有小伙伴靠他拿到字节offer了。 Java基础面试题 Java的特点Java 与 C 的区别JDK/JRE/JVM三者的关系Java程序是编译执行还是解释执行&#xff1f;面向对象和面向过程的区别&#xff1f;面向对象有哪些特性&#xff1f;数组到底是…

适用于电脑的 8 款文件/软件迁移软件 – 快速安全地更换电脑!

将文件/软件从一台设备传输到另一台设备已成为我们日常生活的重要组成部分&#xff0c;无论是出于个人目的还是出于职业目的。在当今快节奏的世界中&#xff0c;我们经常需要在不同设备之间传输大文件&#xff0c;例如视频、照片、文档等。虽然云服务提供了一种共享文件的好方法…

关于Python里xlwings库对Excel表格的操作(二十四)

这篇小笔记主要记录如何【如何使用xlwings库中的“api”类设置单元格边界线型、粗细、颜色】。前面的小笔记已整理成目录&#xff0c;可点链接去目录寻找所需更方便。 【目录部分内容如下】【点击此处可进入目录】 &#xff08;1&#xff09;如何安装导入xlwings库&#xff1b;…

Android--Jetpack--Paging详解

不尝世间醋与墨&#xff0c;怎知人间酸与苦。 择一业谋食养命&#xff0c;等一运扭转乾坤。 你见过哪些令你膛目结舌的代码技巧&#xff1f; 文章目录 不尝世间醋与墨&#xff0c;怎知人间酸与苦。择一业谋食养命&#xff0c;等一运扭转乾坤。你见过哪些令你膛目结舌的代码技…

【GoLang】Go语言几种标准库介绍(三)

文章目录 前言几种库debug 库 (各种调试文件格式访问及调试功能)相关的包和工具&#xff1a;示例 encoding (常见算法如 JSON、XML、Base64 等)常用的子包和其主要功能&#xff1a;示例 flag(命令行解析)关键概念&#xff1a;示例示例执行 总结专栏集锦写在最后 前言 上一篇&a…

【ArcGIS微课1000例】0085:甘肃省白银市平川区4.9级地震震中位置图件制作

据中国地震台网正式测定,12月31日22时27分在甘肃白银市平川区发生4.9级地震,震源深度10公里,震中位于北纬36.74度,东经105.00度。 文章目录 一、白银市行政区划图1. 县级行政区2. 乡镇行政区二、4.9级地震图件制作1. 震中位置2. 影像图3. 震中三维地形一、白银市行政区划图…

【JavaFX】基于JavaFX11 构建可编辑、对象存储、修改立即保存、支持条件过滤的TableView

文章目录 效果设计思路二、使用步骤1. 创建实体类2.读取本地文件数据3. 定义表格TableView总结效果 如图所示,这是一个存储application.properties内容的表格。这里的文件application.properties是从Linux服务器上获取来的。 当点击检索按钮,并输入条件匹配字符时,TableVie…

初识SpringBoot(2023最后一篇文章)

初识SpringBoot 1、SpringBoot概述 Spring是什么&#xff1f; Spring是一个于2003 年兴起的一个轻量级开源Java开发框架&#xff0c;由Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》。Spring是为了解决企业级应用开发的复杂性而创建的&#xff0c;使…

「微服务」微服务架构中的数据一致性

在微服务中&#xff0c;一个逻辑上原子操作可以经常跨越多个微服务。即使是单片系统也可能使用多个数据库或消息传递解决方案。使用多个独立的数据存储解决方案&#xff0c;如果其中一个分布式流程参与者出现故障&#xff0c;我们就会面临数据不一致的风险 - 例如在未下订单的情…

Linux-------rm命令超详解(狠狠爱住)

目录 rm 命令用于在Linux系统中删除指定的文件或目录 基本语法&#xff1a; 常用选项&#xff1a; 示例用法&#xff1a; 放在文末的话&#xff1a; 补充&#xff1a; rm 命令用于在Linux系统中删除指定的文件或目录 基本语法&#xff1a; rm [选项] 文件名/目录名 常用…

一个有趣的MOSFET电路-触摸调光电路

来源 刷B站视频&#xff0c;看到一个很新奇的“触摸调光电路”&#xff0c;电路图如下&#xff1a; 视频在这里&#xff0c;只使用了3个元件。 刚好最近在学模拟电路的 MOSFET&#xff0c;我之前的理解是 MOSFET 的控制电压应该加在 Gate 和 Source 之间&#xff0c;也就是 栅…
最新文章