首页 > 其他分享 >验证二叉搜索树

验证二叉搜索树

时间:2024-11-07 19:43:57浏览次数:6  
标签:node upper lower 验证 LONG 二叉 搜索 long 节点

题目描述

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

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

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

98. 验证二叉搜索树 - 力扣(LeetCode) 

解题思路

要判断一个二叉树是否是有效的二叉搜索树(BST),我们需要确保每个节点都满足BST的定义:节点的左子树只包含小于当前节点的数,节点的右子树只包含大于当前节点的数,并且所有左子树和右子树自身也必须是BST。

递归是解决这个问题的有效方法。递归的基本思路是:

  1. 递归函数定义
    • 定义一个递归函数 isValidBST(TreeNode* node, long long lower, long long upper),其中 node 是当前节点,lower 是当前节点允许的最小值,upper 是当前节点允许的最大值。
    • 初始调用时,lower 可以设为负无穷大(例如 LONG_LONG_MIN),upper 可以设为正无穷大(例如 LONG_LONG_MAX)。
  2. 递归终止条件
    • 如果当前节点为空,返回 true,因为空树是BST。
    • 如果当前节点的值小于等于 lower 或大于等于 upper,返回 false,因为当前节点的值不满足BST的定义。
  3. 递归调用
    • 递归检查左子树,更新 upper 为当前节点的值(因为左子树的所有节点值必须小于当前节点)。
    • 递归检查右子树,更新 lower 为当前节点的值(因为右子树的所有节点值必须大于当前节点)。
  4. 返回结果
    • 如果左子树和右子树都满足BST的定义,返回 true

 

class Solution {
public:
    bool isValidBST(TreeNode* node, long long lower = LONG_LONG_MIN,
                    long long upper = LONG_LONG_MAX) {
        // 空节点是BST
        if (node == nullptr) {
            return true;
        }

        // 当前节点的值不在允许的范围内,不是BST
        if (node->val <= lower || node->val >= upper) {
            return false;
        }

        // 递归检查左子树和右子树
        return isValidBST(node->left, lower, node->val) &&
               isValidBST(node->right, node->val, upper);
    }
};

详细解释

  1. 函数签名
    • isValidBST(TreeNode* node, long long lower = LONG_LONG_MIN, long long upper = LONG_LONG_MAX)
      • node 是当前节点。
      • lower 是当前节点允许的最小值,初始为 LONG_LONG_MIN
      • upper 是当前节点允许的最大值,初始为 LONG_LONG_MAX
  2. 递归终止条件
    • if (node == nullptr) { return true; }:空节点是BST。
    • if (node->val <= lower || node->val >= upper) { return false; }:当前节点的值不在允许的范围内,不是BST。
  3. 递归调用
    • isValidBST(node->left, lower, node->val):检查左子树,更新 upper 为当前节点的值。
    • isValidBST(node->right, node->val, upper):检查右子树,更新 lower 为当前节点的值。
  4. 返回结果
    • return isValidBST(node->left, lower, node->val) && isValidBST(node->right, node->val, upper);:如果左子树和右子树都满足BST的定义,返回 true

标签:node,upper,lower,验证,LONG,二叉,搜索,long,节点
From: https://blog.csdn.net/2302_80190174/article/details/143606226

相关文章

  • 大语言模型是搜索匹配还是智能生成?
    随着人工智能技术的迅猛发展,尤其是大语言模型(如GPT-3、GPT-4等)的问世,许多人开始讨论这些模型到底是依靠“搜索匹配”还是“智能生成”来回答问题、生成文本。这个问题关系到大语言模型的本质及其应用前景,对AI的认知和使用也有深远影响。在辩论这一话题时,我们可以从以下几个方......
  • vue项目滑动验证组件
    父组件---表单部分:<el-form-itemprop="phone"style="margin-top:6%"><el-inputv-model="ruleForm.phone"placeholder="请输入手机号"clearable:readonly="st......
  • .net网页验证码、登录验证码
    来源:https://blog.csdn.net/Yuhang_Zhou/article/details/140614304验证码辅助类usingSystem.Drawing;usingSystem.Drawing.Imaging;namespaceXCGApp{///<summary>///验证码辅助类///</summary>publicclassValidateCodeUtil{/......
  • 京东创作平台旋转验证码识别
    昨天京东创作平台验证码又更新了,变成了这种旋转验证码。经过我们一天的努力,终于完成了这款验证码的数据标记,模型训练。现在正确率达到了几乎100%。识别代码只需要获取图片链接,下载图片得到原图,使用下面代码就可以识别角度,然后根据角度计算滑动距离,就可以自动完成验证impor......
  • 路径分析算法—基于A*算法的路径搜索
    原文链接:路径分析算法—基于A*算法的路径搜索–每天进步一点点A*算法擅长解决静态路径中最短路径问题,而又不同于Dijkstra算法和Floyd算法,该算法综合了广度优先搜索(BreadthFirstSearch)和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评......
  • Java深度优先搜索(DFS)算法实现
    标题:Java深度优先搜索(DFS)算法实现引言:深度优先搜索(Depth-FirstSearch,DFS)是一种常用的图遍历算法,它通过递归地遍历图中的每个顶点,来寻找特定的路径或解决某些问题。本篇博客将介绍如何用Java语言实现深度优先搜索算法。算法思想:深度优先搜索算法的基本思想是先访问一个......
  • AI 搜索来势汹汹,互联网将被颠覆还是进化?
    最近,美国新闻集团起诉了知名AI搜索引擎PerplexityAI。也许你会想,这不就是又一起“AI惹官司”吗?其实,这次情况不太一样,甚至可能会改变我们未来上网的方式!争议的焦点是什么?是未来的AI搜索——即那些能从全网总结信息的“AI答题王”。这些AI不只是简单的聊天机器人,而是能......
  • 基于信息增益和基尼指数的二叉决策树
    #coding:UTF-8'''基于信息增益和基尼指数的二叉决策树的实现。该决策树可以用于分类问题,通过选择合适的特征来划分样本。'''fromcollectionsimportCounterclassbiTree_node:'''二叉树节点定义每个节点可以是叶子节点或内部节点。'''def_......
  • 华为OD机试真题-数组二叉树码-2024年OD统一考试(E卷)
    最新华为OD机试考点合集:华为OD机试2024年真题题库(E卷+D卷+C卷)_华为od机试题库-CSDN博客     每一题都含有详细的解题思路和代码注释,精编c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看,发现新题及时跟新。题目描述二叉树也可以用数组来......
  • 数据结构 ——— 链式二叉树oj题:相同的树
    目录题目要求手搓两个链式二叉树代码实现 题目要求给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。手搓两个链式二叉树代码演示://数据类型typedefintBTDataType;......