LeetCode 98 验证二叉搜索树

题目描述

验证二叉搜索树

给你一个二叉树的根节点 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:递归

设计一个递归函数 helper(root, lower, upper) 来递归判断,函数表示考虑以 root 为根的子树,判断子树中所有节点的值是否都在 (l,r) 的范围内(注意是开区间)。

如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回,否则我们要继续递归调用检查它的左右子树是否满足,如果都满足才说明这是一棵二叉搜索树。

那么根据二叉搜索树的性质:

  • 在递归调用左子树时,我们需要把上界 upper 改为 root.val,即调用 helper(root.left, lower, root.val),因为左子树里所有节点的值均小于它的根节点的值。
  • 在递归调用右子树时,我们需要把下界 lower 改为 root.val,即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf), inf 表示一个无穷大的值。

java代码:

/**
 * 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) {
        return isValidBST (root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST (TreeNode root, long lower, long upper) {
        if (root == null) {
            return true;
        }
        if (root.val <= lower || root.val >= upper) {
            return false;
        }
        return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);
    }
}

复杂度

  • 时间复杂度:O(n) ,其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次。
  • 空间复杂度:O(n),递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,即二叉树的高度。最坏情况下二叉树为一条链,树的高度为 n ,递归最深达到 n 层。

解法2:中序遍历

二叉搜索树「中序遍历」得到的值构成的序列一定是升序的,这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。

使用栈模拟中序遍历。

java代码:

class Solution {
    public boolean isValidBST(TreeNode root) {
        long preVal = Long.MIN_VALUE;
        Deque<TreeNode> stk = new LinkedList<>();
        while (root != null || !stk.isEmpty()) {
            // 一直遍历左节点到叶子节点
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            // 然后依次弹栈,为左树节点
            root = stk.pop();
            if (root.val <= preVal) {
                return false;
            }
            preVal = root.val;
            // 再遍历右树节点
            root = root.right;
        }
        return true;
    }
}

复杂度

  • 时间复杂度:O(n)
  • 空间复杂度:O(n),其中 n 为二叉树的节点个数。栈最多存储 n 个节点,因此需要额外的 O(n) 的空间。

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

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

相关文章

VM虚拟机Linux系统Redhat7.4版本进行网络配置

日常中自己搭建的虚拟机一般用到两种网络方式&#xff0c;第一种是仅主机模式、还有一种是NAT模式。 1、仅主机模式&#xff1a;可以和自己本地电脑&#xff0c;或者虚拟机和虚拟机之间进行网络通信&#xff0c;相当于一个局域网&#xff0c;是不能连接外网的。 2、NAT模式&a…

数据结构篇:深度剖析跳跃表及与B+树优劣分析

本文旨在探讨跳跃表的特性及其在实际应用场景中的作用&#xff0c;同时对其与B树进行比较&#xff0c;以帮助更好地理解和运用这两种数据结构。 跳跃表 什么是跳跃表&#xff08;skip list&#xff09; 跳跃表是一种基于跳跃链表的有序数据结构&#xff0c;它是一种多层链表&…

openGauss_5.1.0 企业版快速安装及数据库连接:单节点容器化安装

目录 &#x1f4da;第一章 官网信息&#x1f4da;第二章 安装&#x1f4d7;下载源码&#x1f4d7;下载安装包&#x1f4d7;修改版本&#x1f4d7;解压安装包&#x1f4d7;运行buildDockerImage.sh脚本&#x1f4d7;docker操作&#x1f4d5;查看docker镜像&#x1f4d5;启动dock…

上位机图像处理和嵌入式模块部署(改进的qmacvisual动态插件卸载)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面我们讨论过&#xff0c;qmacvisual虽然提供了很多的功能&#xff0c;包括的种类很多&#xff0c;但是总有一些功能是客户希望定制的。这些都是…

更改docker镜像下载地址

一.简介 使用指令 sudo docker info 查看本机的docker镜像下载地址为 由于本机的var文件空间不足&#xff0c;因此&#xff0c;想更改他的存储地址&#xff0c;如下 二.开始操作 1.停止Docker服务&#xff1a; 执行命令 sudo systemctl stop docker 以及 sudo systemctl s…

USB端口

winx&#xff0c;打开设备管理器 名称解释 HS-USB 分类全称传输速率版本超速SSsuper-speed最大速率5Gbps、10Gbps、20GbpsUSB3.0~USB3.2高速HShigh-speed25Mbps-400 Mbps &#xff08;最大480 Mbps&#xff09;USB2.0全速FSfull-speed500Kbps-10Mbps&#xff08;最大12Mbps&…

8个Python小游戏,小白练手,我都能玩一天【内附源码】

大家好&#xff0c;在使用Python的过程中&#xff0c;我最喜欢的就是Python的各种第三方库&#xff0c;能够完成很多操作。 下面就给大家介绍8个通过Python构建的项目&#xff0c;以此来学习Python编程。 大家也可根据项目的目的及提示&#xff0c;自己构建解决方法&#xff…

c++ stub函数打桩

应用场景&#xff1a; 当我们在开发一个涉及到第三方sdk库的软件时&#xff0c;比如做一个上位机控制客户端&#xff0c;该客户端当中调用了一份sdk库当中的接口。而这份sdk库&#xff0c;作为上层客户端软件与下层设备进行通信的媒介&#xff0c;可能需要在有真实设备的环境下…

社交网络与Web3:数字社交的演进

在数字化时代的浪潮下&#xff0c;社交网络已成为人们日常生活的重要组成部分。从早期的在线论坛到如今的社交媒体平台&#xff0c;社交网络已经成为人们交流、分享和获取信息的主要渠道。然而&#xff0c;随着区块链技术的发展&#xff0c;传统的社交网络正经历着一场革命性的…

Sy7 shell编程-1

实验环境&#xff1a; 宿主机为win11&#xff0c;网络&#xff1a;10.255.50.5 6389 WSL2 ubuntu 目标机的OS&#xff1a;Ubuntu 内核、版本如下&#xff1a; linuxpeggy0223:/$ uname -r 5.15.146.1-microsoft-standard-WSL2 linuxpeggy0223:/$ cat /proc/version Linux vers…

Java | Leetcode Java题解之第22题括号生成

题目&#xff1a; 题解&#xff1a; class Solution {static List<String> res new ArrayList<String>(); //记录答案 public List<String> generateParenthesis(int n) {res.clear();dfs(n, 0, 0, "");return res;}public void dfs(int n ,int…

动态规划应用

介绍 是用来解决一类最优问题的算法思想&#xff0c;将一个复杂的问题分解成若干个子问题&#xff0c;通过综合子问题的最优解得到。 递归写法实例 优化斐波那契数列 int F(int n){if(n0||n1) return 1;else{return F(n-1)F(n-2);}有太多重复计算&#xff0c;可用一个数组记…

oracle数据库怎么查看当前登录的用户?

方法如下&#xff1a; 输入select * from dba_users; 即可。 常用语句&#xff1a; 一&#xff0c;查看数据库里面所有用户&#xff1a; select * from dba_users; 前提是你是有dba权限的帐号&#xff0c;如sys,system。 二&#xff0c;查看你能管理的所有用户&#xff1…

.[[backup@waifu.club]].svh勒索病毒数据怎么处理|数据解密恢复

尊敬的读者&#xff1a; 近年来&#xff0c;随着信息技术的迅猛发展&#xff0c;网络安全问题日益凸显&#xff0c;其中勒索病毒成为了一大威胁。.[[backupwaifu.club]].svh、.[[MyFilewaifu.club]].svh勒索病毒就是其中之一&#xff0c;它以其独特的传播方式和恶劣的加密手段…

Spring AMQP消息中间件

SpringAMQP简单说就是一个中间件&#xff0c;提供了模板方便我们操作各种消息模型 上面已经学了RabbitMQ消息队列是有五种消息模型&#xff0c;并且我们演示了其中的基本消息队列(Hello World)。用的是官方API&#xff0c;来实现的基本消息队列(Hello World)。会发现官方提供的…

华为OD-C卷-攀登者1[100分]

攀登者喜欢寻找各种地图,并且尝试攀登到最高的山峰。 地图表示为一维数组,数组的索引代表水平位置,数组的元素代表相对海拔高度。其中数组元素0代表地面。 例如: [0,1,2,4,3,1,0,0,1,2,3,1,2,1,0],代表如下图所示的地图 地图中有两个山脉位置分别为 1,2,3,4,5 和 8,9,1…

一、OpenCvSharp环境搭建

一、Visual Studio 创建新项目 二、选择Windows窗体应用&#xff08;.NET Framework&#xff09; 直接搜索模板&#xff1a;Windows窗体应用(.NET Framework) 记得是C#哈&#xff0c;别整成VB(Visual Basic)了 PS&#xff1a;若搜索搜不到&#xff0c;直接点击安装多个工具和…

K8S哲学 - 常见的资源类型

资源类型 namespace kubectl apply 和 kubectl create kubectl apply是声明式的 和 kubectl create是命令式的对吗 deployment 和 job的区别

Fiddle配置代理,保手机模拟器访问外部网络

前言&#xff1a; 嘿&#xff01;大家好&#xff01;我来带你们玩转Fiddler和Mumu模拟器的组合技了&#xff01;此组合技能帮助你实现在模拟器上畅游外部网络。相信我&#xff0c;它会让你的开发和测试过程更加轻松愉快&#xff01;废话不多说&#xff0c;赶紧展开我们的冒险吧…

bugku-web-file_get_contents

<?php extract($_GET); if (!empty($ac)){$f trim(file_get_contents($fn));if ($ac $f){echo "<p>This is flag:" ." $flag</p>";}else{echo "<p>sorry!</p>";} } ?> 这里涉及到几个不常用的函数 这里直接构…