力扣日记12.21【二叉树篇】98. 验证二叉搜索树

力扣日记:【二叉树篇】98. 验证二叉搜索树

日期:2023.12.21
参考:代码随想录、力扣

98. 验证二叉搜索树

题目描述

难度:中等

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

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

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

示例 1:
在这里插入图片描述

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

示例 2:
在这里插入图片描述

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

提示:

  • 树中节点数目范围在[1, 10^4] 内
  • -2^31 <= Node.val <= 2^31 - 1

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
#define SOLUTION 2
public:
#if SOLUTION == 0
    // 下面代码有问题,搞不定了。。。
    /*
    bool isValidBST(TreeNode* root) {
        if (root == nullptr)    return false;
        // 需要先对根节点进行处理
        if (root->left != nullptr && root->left->val >= root->val)  return false;
        if (root->right != nullptr && root->right->val <= root->val)    return false;
        // 根节点暂且满足条件,递归判断其子树  
        return traversal(root->left, root->val, true) && traversal(root->right, root->val, false);
    }
    // 参数为当前子树的根节点,以及该子树的父节点的值,以及该子树是左子树还是右子树,返回值为该子树是否为二叉搜索树
    bool traversal(TreeNode* root, int midNodeVal, bool leftTree) {
        if (root == nullptr)    return true;
        // 左为空,则左不为false
        // 左不为空, 
        if (root->left != nullptr) {
            // 首先判断左子节点
            if (root->left->val >= root->val)   return false;
            if (!leftTree) {
                // 如果是右子树,还要保证其左节点比该子树的父节点大
                if (root->left->val <= midNodeVal)  return false;
            }
        }  
        if (root->right != nullptr) {
            // 首先判断右子节点
            if (root->right->val <= root->val)  return false;
            if (leftTree) {
                // 如果是左子树,要保证其右节点比该子树的父节点小
                if (root->right->val >= midNodeVal) return false;
            }
        }
        // 遍历左右节点
        bool left = traversal(root->left, root->val, true);
        if (left == false)  return false;
        bool right = traversal(root->right, root->val, false);
        return right;
    }
    */
#elif SOLUTION == 1
    // 思路:利用二叉搜索树的特性!!!
    // 二叉搜索树中序遍历是有序的!!!
    // 方式1:先转换为数组,再判断数组是否有序
    bool isValidBST(TreeNode* root) {
        // 先中序遍历得到数组
        vector<int> result;
        traversal(root, result);
        // 对数组进行判断
        // 如果数组为空或只有1个,则为true(空的树也为二叉搜索树!)
        if (result.size() <= 1) return true;
        // size >= 2
        // 遍历数组
        for (int i = 1; i < result.size(); i++) {
            // 如果后面的元素 <= 前面的元素(注意也不能相等),则不是二叉搜索树
            if (result[i] <= result[i-1])   return false;
        }
        return true;
    }
    // 中序遍历:左中右
    void traversal(TreeNode* root, vector<int>& result) {
        if (root == nullptr)   return;
        // 左
        traversal(root->left, result);
        // 中
        result.push_back(root->val);
        // 右
        traversal(root->right, result);
    }
#elif SOLUTION == 2
    // 方式2:直接在进行中序遍历的同时判断是否有序
    TreeNode* pre = nullptr;    // 保存上一个节点(用来比较)
    bool isValidBST(TreeNode* root) {
        // 空,直接返回true
        if (root == nullptr)    return true;
        // 左
        bool left = isValidBST(root->left);
        if (left == false)  return false;
        // 中
        // 如果pre不为空,当前节点值需要比上一个节点值大
        if (pre != nullptr && root->val <= pre->val)    return false;   // false 则不需要继续迭代了也不需要更新pre了
        // 如果没有违反,更新pre,并继续递归
        pre = root;
        // 右
        bool right = isValidBST(root->right);
        return right;
    }
#endif
};

复杂度

时间复杂度:
空间复杂度:

思路总结

  • 本题就像是脑筋急转弯,得从二叉搜索树转到这样一个思路:
  • 如果一棵树是二叉搜索树,其中序遍历一定是有序的!!!(从小到大)
  • 因此,本题有两种方式来验证:
    • 方式1:先用中序遍历(左中右)得到遍历数组;再对数组判断是否有序(较简单)
    • 方式2:直接在中序遍历的同时判断是否有序(需要在递归中保存上一个值,稍复杂)

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

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

相关文章

VLOOKUP中的#N/A错误很常见,这里有详细排除步骤

你的VLOOKUP是否提取了错误的数据&#xff0c;或者你根本无法使其工作&#xff1f;本教程展示了如何快速修复常见的VLOOKUP中的#N/A错误并克服其主要限制。 ​在VLOOKUP公式中&#xff0c;当Excel找不到查找值时&#xff0c;会显示#N/A错误消息&#xff08;意思是“不可用”&a…

目标检测入门体验,技术选型,加载数据集、构建机器学习模型、训练并评估

Hi, I’m Shendi 1、目标检测入门体验&#xff0c;技术选型&#xff0c;加载数据集、构建机器学习模型、训练并评估 在最近有了个物体识别的需求&#xff0c;于是开始学习 在一番比较与询问后&#xff0c;最终选择 TensorFlow。 对于编程语言&#xff0c;我比较偏向Java或nod…

冬至快乐Happy winter solstice

冬至通常是每年的12月21日到12月23日之间&#xff0c;在这一天&#xff0c;白昼时间是全年最短的一天&#xff0c;夜晚是全年时间最长的一天“Winter Solstice” falls between the periods of December 21 to December 23. On this day, the day is the shortest and night is…

VS+Qt 打包Python文件

书接上回&#xff0c;调用C调用python&#xff0c;下面来谈谈随exe文件打包。 先说下环境vs2019Qt5.12.11python3.8&#xff0c;这里需要注意如果你要适配Win7的系统&#xff0c;python最好是9以下&#xff0c;以上不兼容&#xff0c;也没时间找方法&#xff0c;找到评论说下 如…

【MYSQL】MYSQL 的学习教程(三)之索引核心知识点

1. 什么是索引&#xff1f; 索引是一种能提高数据库查询效率的数据结构&#xff0c;一般存储在磁盘的文件中&#xff0c;它是占用物理空间的 适当的索引能提高查询效率&#xff0c;过多的索引会影响数据库表的插入和更新功能。 2. 索引的优劣势 优势&#xff1a; 提高数据…

鸿蒙-HarmonyOS之初见

鸿蒙初识&#xff0c;此事能成&#xff01;&#xff01; 自己安装工具、配置环境并运行成功&#xff0c;流程记录。 一、首先官网下载开发工具 官网地址&#xff1a;https://developer.huawei.com/consumer/cn/ 当前最新的版本3.1 &#xff0c;windows和Mac&#xff0c;Mac又…

信息论安全与概率论

目录 一. Markov不等式 二. 选择引理 三. Chebyshev不等式 四. Chernov上限 4.1 变量大于 4.2 变量小于 信息论安全中会用到很多概率论相关的上界&#xff0c;本文章将梳理几个论文中常用的定理&#xff0c;重点关注如何理解这些定理以及怎么用。 一. Markov不等式 假定…

【Spring】15 ApplicationContextAware 接口

文章目录 1. 简介2. 作用3. 使用3.1 创建并实现接口3.2 配置 Bean 信息3.3 创建启动类3.4 启动 4. 应用场景总结 Spring 框架提供了许多回调接口&#xff0c;用于在 Bean 的生命周期中执行特定的操作。ApplicationContextAware 接口是其中之一&#xff0c;它允许 Bean 获取对 A…

Jenkins的文档翻译

官网Jenkins.io Jenkins用户文档 欢迎来到Jenkins用户文档-为那些想要使用Jenkins的现有功能和插件特性的人。如果你想通过开发自己的Jenkins插件来扩展Jenkins的功能&#xff0c;请参考extend Jenkins(开发者文档)。 詹金斯是什么? Jenkins是一个独立的、开源的自动化服务…

程序员的23大IONIO面试问题及答案

文章目录 1. 什么是IO流&#xff1f;2.java中有几种类型的流&#xff1f;3.字节流和字符流哪个好&#xff1f;怎么选择&#xff1f;4.读取数据量大的文件时&#xff0c;速度会很慢&#xff0c;如何选择流&#xff1f;5. IO模型有几种&#xff1f;6.阻塞IO &#xff08;blocking…

QT基础介绍

QT介绍 QT 是跨平台的c开发库&#xff0c;主要用来开发图形用户界面&#xff08;Graphical User Interface&#xff0c;GUI&#xff09;程序&#xff0c;当然也可以开发不带界面的命令行&#xff08;command user interface&#xff0c;CUI&#xff09;程序。 Qt中文官网&…

Linux磁盘空间不足扩展

先在虚拟机Vmware上扩展磁盘空间 后将fdisk 进行分区之后&#xff0c;在/dev/中找不到新分区文件 3.创建物理卷pv时发现找不到/dev/sda3分区&#xff0c;通过ls查看确认在/dev/中没有找到新分区文件 4.解决方法 执行&#xff1a;partprobe 再查看/dev中是否可以看到新分区文件…

python爬虫小案例:获取B*站视频数据

嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 第三方模块: requests >>> pip install requests 如何安装python第三方模块: win R 输入 cmd 点击确定, 输入安装命令 pip install 模块名 (pip install requests) 回车 在pycharm中点击Terminal(终端) 输入安装…

XM平台官网开户注册流程图解

注册前准备 在进行XM外汇官网注册之前&#xff0c;首先需要准备必要的信息&#xff0c;包括个人身份信息、联系方式以及相关财务信息。确保这些信息的准确性是保证注册流程顺利进行的关键。 一、要访问XM外汇官方网站&#xff0c;首先打开您的浏览器。在浏览器的地址栏中输入…

fill-in-the-middle(FIM) 实现与简单应用

1 背景 传统训练的 GPT 模型只能根据前文内容预测后文内容&#xff0c;但有些应用比如代码生成器&#xff0c;需要我们给出上文和下文&#xff0c;使模型可以预测中间的内容&#xff0c;传统训练的 GPT 就不能完成这类任务。 传统训练的 GPT 只能根据上文预测下文 使用 FIM…

Pytest小技巧:高效获取自动化测试结果

自动化测试用例在执行完成后&#xff0c;我们想要很清楚的查看到测试用例的执行结果&#xff0c;我们可以通过Pytest中的Hooks来进行获取吗&#xff1f; 其中Pytest中存在多个Hooks的函数&#xff0c;小编今天先简单介绍其中一种&#xff0c;通过pytest_runtest_makereport 获…

多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测

多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测 目录 多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 多维时序 | MATLAB实现…

unity2d 关闭全局重力

UNITY2D项目默认存在Y轴方向重力&#xff0c;创建俯视角2D场景时可通过以下配置关闭 Edit > Project Settings > Physics 2D > General Settings > Gravity 设置Y0

vue3引入高德地图报错Uncaught Error: Invalid Object: LngLat(NaN, NaN

问题&#xff1a; 原因&#xff1a;容器高度未设置 解决&#xff1a; 地图容器添加高度。 <style scoped> #map {width: 100%;height: 800px; } </style>

本地配置Java支付宝沙箱环境模拟支付并内网穿透远程调试

文章目录 前言1. 下载当面付demo2. 修改配置文件3. 打包成web服务4. 局域网测试5. 内网穿透6. 测试公网访问7. 配置二级子域名8. 测试使用固定二级子域名访问 前言 在沙箱环境调试支付SDK的时候&#xff0c;往往沙箱环境部署在本地&#xff0c;局限性大&#xff0c;在沙箱环境…