98. 验证二叉搜索树

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

解题思路:

二叉搜索树的定义:

二叉搜索树或者是一颗空树,或者是具有如下性质的二叉树:

  1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值
  2. 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
  3. 它的左、右子树也分别为二叉搜索树。

方法一:中序遍历

 二叉搜索树中序遍历得到的结果一定是升序的,所以可以先得到树中所有节点中序遍历的值,然后在判断中序遍历得到的集合是否是升序的,如果是,返回true,否则返回false

AC代码:

/**
 * 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 {
    List<Integer> list=new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        if (root==null){
            return true;
        }
        inOrderTraversal(root);
        int pre = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            int cur = list.get(i);
            if (cur<=pre){
                return false;
            }
            pre=cur;
        }
        return true;
    }
    
    public void inOrderTraversal(TreeNode root){
        if (root==null){
            return;
        }
        inOrderTraversal(root.left);
        list.add(root.val);
        inOrderTraversal(root.right);
    }
}

方法二: 递归

二叉搜索树的定义是递归的,可以递归的判断左右子树是否是二叉搜索树。

根节点的值确定后,左子树中所有节点的值都要小于根节点,右子树中所有节点的值都要大于根节点,所以可以使用 min 和 max 两个变量标记当前二叉搜索树中所有节点值的范围。具体算法如下:

  1. 定义递归函数:isValidBST(TreeNode root, long min, long max),判断当前二叉树是否是二叉搜索树,并且需要满足所有节点值的范围在 (min,max)区间内。
  2. 递归终止条件:如果 root==null,返回true
  3. 否则:
    1. 如果root节点的值不在区间 (min,max) 内,说明不是一个二叉搜索树,返回false
    2. 递归的判断左子树的是否是二叉搜索树:isValidBST(root.left, min, root.val),此时左子树节点所有节点值都要小于根节点,即最大值不能大于 root.val,更新 max=root.val
    3. 递归的判断右子树的是否是二叉搜索树:isValidBST(root.left, root.val, max),此时右子树节点所有节点值都要大于根节点,即最小于值不能小于 root.val,更新 min=root.val
    4. return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
  4. 注意:因为节点值得大小范围为 int 类型得最小值 至 最大值之间,所以初始值,min= Long.MIN_VALE,max=Long.MAX_VALUE;

AC代码:

/**
 * 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) {
        if (root == null) {
            return true;
        }
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (min >= root.val || max <= root.val) {
            return false;
        }
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

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

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

相关文章

OpenCV官方教程中文版 —— Hough 直线变换

OpenCV官方教程中文版 —— Hough 直线变换 前言一、原理二、OpenCV 中的霍夫变换三、Probabilistic Hough Transform 前言 目标 • 理解霍夫变换的概念 • 学习如何在一张图片中检测直线 • 学习函数&#xff1a;cv2.HoughLines()&#xff0c;cv2.HoughLinesP() 一、原理…

C++ priority_queue 的使用

1. priority_queue 的介绍 下面是 priority_queue 的介绍&#xff0c;来自于&#xff1a;&#x1f3f9;priority_queue - C Reference (cplusplus.com) 的中文翻译&#xff0c;您可以尝试看看。 优先队列是一种容器适配器&#xff0c;根据严格的弱排序标准&#xff0c;它的第一…

实战 | 记一次红队打的逻辑漏洞

八月初参加某市演练时遇到一个典型的逻辑漏洞&#xff0c;可以绕过验证码并且重置任意用户的密码。 首先访问页面&#xff0c;用户名处输入账号会回显用户名称&#xff0c;输入admin会回显系统管理员。&#xff08;hvv的时候蓝队响应太快了&#xff0c;刚把admin的权限拿到了&a…

视频无痕去水印怎么去,这三个神器轻松去除

视频无痕去水印怎么去&#xff1f;各位小伙伴在初学剪视频的时候是不是和我一样经常会碰到一个烦人的问题&#xff1a;在网上找到的视频素材总是带着讨厌的水印&#xff0c;不仅影响美观还挡住了视频的一些部分&#xff0c;让人特别不爽&#xff0c;我想各位遇到这种情况的时候…

框架安全-CVE 漏洞复现DjangoFlaskNode.jsJQuery框架漏洞复现

目录 服务攻防-框架安全&CVE复现&Django&Flask&Node.JS&JQuery漏洞复现中间件列表介绍常见语言开发框架Python开发框架安全-Django&Flask漏洞复现Django开发框架漏洞复现CVE-2019-14234&#xff08;Django JSONField/HStoreField SQL注入漏洞&#xff…

安装虚拟机(VMware)保姆级教程及配置虚拟网络编辑器和安装WindowsServer以及宿主机访问虚拟机和配置服务器环境

目录 一、操作系统 1.1.什么是操作系统 1.2.常见操作系统 1.3.个人版本和服务器版本的区别 1.4.Linux的各个版本 二、VMware Wworkstation Pro虚拟机的安装 1.下载与安装 注意&#xff1a;VMWare虚拟网卡 2.配置虚拟网络编辑器 三、安装配置 WindowsServer 1.创建虚拟…

AS/400-物理文件-02

物理文件 - Physical file Physical file物理文件中的条目级别相关命令 Physical file 简介物理文件 这是一个文件。包含预定义的结构化格式的数据。它是PF类型。通过使用CRTPF命令创建PF。PF中包含的字段的最大数量为8000。最多包含120个关键字段。 PF 的结构如下 TYPE SPECIF…

题目描述:输入数字,第一行为数组的大小,第二行为数组的值。求其中相邻两个数字相差不大于8的最大片段的长度。

题目描述&#xff1a; 输入数字&#xff0c;第一行为数组的大小&#xff0c;第二行为数组的值。求其中相邻两个数字相差不大于8的最大片段的长度。 示例1&#xff1a; 输入&#xff1a;91 2 4 6 12 2 8 6 4 输出&#xff1a;5示例2&#xff1a; 输入&#xff1a;101 4 5 6 2…

分布式:一文吃透分布式锁,Redis/Zookeeper/MySQL实现

目录 一、项目准备spring项目数据库 二、传统锁演示超卖现象使用JVM锁解决超卖解决方案JVM失效场景 使用一个SQL解决超卖使用mysql悲观锁解决超卖使用mysql乐观锁解决超卖四种锁比较Redis乐观锁集成Redis超卖现象redis乐观锁解决超卖 三、分布式锁概述四、Redis分布式锁实现方案…

干货!数字IC后端入门学习笔记

很多同学想要了解IC后端&#xff0c;今天大家分享了数字IC后端的学习入门笔记&#xff0c;供大家学习参考。 很多人对于后端设计的概念比较模糊&#xff0c;需要做什么也都不甚清楚。 有的同学认为就是跑跑 flow、掌握各类工具。 事实上&#xff0c;后端设计的工作远不止于此。…

状态模式-对象状态及其转换

某信用卡业务系统&#xff0c;银行账户存在3种状态&#xff0c;且在不同状态下存在不同的行为&#xff1a; 1&#xff09;正常状态&#xff08;余额大等于0&#xff09;&#xff0c;用户可以存款也可以取款&#xff1b; 2&#xff09;透支状态&#xff08;余额小于0且大于-20…

【HarmonyOS】鸿蒙操作系统架构

HarmonyOS架构 一. 鸿蒙系统定位二. 架构整体遵从分层设计三. HarmonyOS具有的技术特性四. HarmonyOS有三大特征 其它相关推荐&#xff1a; 软考系统架构之案例篇(架构设计相关概念) 系统架构之微服务架构 系统架构设计之微内核架构 所属专栏&#xff1a;系统架构设计师 一. 鸿…

软考系列(系统架构师)- 2013年系统架构师软考案例分析考点

试题一 软件架构&#xff08;根据描述填表、ESB 定义和功能&#xff09; 【问题1】&#xff08;10分&#xff09; 服务建模是对Ramp Coordination信息系统进行集成的首要工作&#xff0c;公司的架构师首先对Ramp Coordination信息系统进行服务建模&#xff0c;识别出系统中的两…

window11 更改 vscode 插件目录,释放C盘内存

由于经常使用vscode开发会安装一些代码提示插件&#xff0c;然后C盘内容会逐渐缩小&#xff0c;最终排查定位到vscode。这个吃内存不眨眼的家伙。 建议&#xff1a;不要把插件目录和vscode安装目录放在同一个位置&#xff0c;不然这样vscode更新后&#xff0c;插件也会消失。 v…

OpenCV官方教程中文版 —— 2D 直方图

OpenCV官方教程中文版 —— 2D 直方图 前言一、介绍二、OpenCV 中的 2D 直方图三、Numpy 中 2D 直方图四、绘制 2D 直方图 前言 本节我们会学习如何绘制 2D 直方图&#xff0c;我们会在下一节中使用到它。 一、介绍 在前面的部分我们介绍了如何绘制一维直方图&#xff0c;之…

轻量级 IDE 文本编辑器 Geany 发布 2.0

Geany 是功能强大、稳定、轻量的开发者专用文本编辑器&#xff0c;支持 Linux、Windows 和 macOS&#xff0c;内置支持 50 多种编程语言。 2005 年Geany 发布首个版本 0.1。上周四刚好是 Geany 诞生 18 周年纪念日&#xff0c;官方发布了 2.0 正式版以表庆祝。 下载地址&#…

【机器学习可解释性】2.特征重要性排列

机器学习可解释性 1.模型洞察的价值2.特征重要性排列3.部分依赖图4.SHAP 值5.SHAP值的高级使用 正文 前言 你的模型认为哪些特征最重要&#xff1f; 介绍 我们可能会对模型提出的最基本的问题之一是&#xff1a;哪些特征对预测的影响最大&#xff1f; 这个概念被称为特征重…

antd+全屏的坑(全屏下a-modal/下拉框等不展示)

问题&#xff1a;针对某个元素全屏时&#xff0c;下拉框/弹窗/二次确认窗不展示&#xff1a;下拉框是往body里面插入的&#xff0c;全屏的元素盖住了下拉框。解决&#xff1a;给有下拉框的加入:append-to-body"false"&#xff08;缺点&#xff1a;每个都需要加&#…

Ansible中常用模块

1.ansible实现管理的方式 Ad-Hoc //利用ansible命令直接完成管理&#xff0c;主要用于临时命令使用场景 playbook //ansible脚本&#xff0c;主要用于大型项目场景&#xff0c;需要前期的规划 2.Ad-Hoc执行方式中如何获得帮助 ansible-doc …

测试C#调用Aplayer播放视频(1:加载Aplayer控件)

微信公众号“Dotnet跨平台”的文章《开源精品&#xff0c;使用 C# 开发的 KTV 点歌项目》中使用了迅雷开源APlayer播放引擎。最近在学习有哪些能拿来播放视频的组件或控件&#xff0c;于是准备试试&#xff0c;根据文章中的介绍&#xff0c;在迅雷APlayer播放引擎网站中下载了A…