leetcode每日一练-第98题- 验证二叉搜索树

这篇具有很好参考价值的文章主要介绍了leetcode每日一练-第98题- 验证二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode每日一练-第98题- 验证二叉搜索树,算法,开发语言,c++

leetcode每日一练-第98题- 验证二叉搜索树,算法,开发语言,c++ 

 

一、思路

因为要验证多个节点是否是二叉搜索树,因此使用递归

二、解题方法

设计一个递归函数 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 表示一个无穷大的值。

三、code

class Solution {
public:

    bool helper(TreeNode* root,long long lower,long long upper)
    {
        if(root==nullptr)
        {
            return true;// 基本情况:子树为空,认为是合法的BST
        }
        if(root->val <= lower || root->val >= upper)
        {
            return false;// 节点值不在允许范围内,子树不是有效的BST
        }
        return helper(root->left,lower,root->val)&&helper(root->right,root->val,upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root,LONG_MIN,LONG_MAX);

    }
};

 =========================================================================学到的知识:

①当程序需要多次检验是否符合条件时,

需要用到递归方法

②结点的值

root->val文章来源地址https://www.toymoban.com/news/detail-608314.html

到了这里,关于leetcode每日一练-第98题- 验证二叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode98. 验证二叉搜索树

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给你一个二叉树的根节点  root  ,判断其是否是一个有效的二叉搜索树。 有效  二叉搜索树定义如下: 节点的左子树只包含  小于  当前节点的数。 节点的右子树只包含  大于  当前节点的数。 所有左子树和右子树自身

    2024年02月11日
    浏览(37)
  • LeetCode 98. 验证二叉搜索树

    ​ 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1: ​​​​ 输入:root = [2,1,

    2024年02月09日
    浏览(30)
  • leetcode做题笔记98. 验证二叉搜索树

    给你一个二叉树的根节点  root  ,判断其是否是一个有效的二叉搜索树。 有效  二叉搜索树定义如下: 节点的左子树只包含  小于  当前节点的数。 节点的右子树只包含  大于  当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 本题要判断二叉树是否为二叉

    2024年02月11日
    浏览(35)
  • LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)

    这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos 做这道题之前,我反复审题,最后确认:没错,不存在什么坑,这道题确实非常非常简单,然而却被官方定义为 中等 难度 这一定是送分,白捡一道中等难度题,接下来,一起来轻松愉快的享受解题

    2024年02月09日
    浏览(33)
  • 98. 验证二叉搜索树

    98. 验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree/ //保证按照规则来,往左边走就要,不能比当前值还大了;往右边走就要,不能比当前值还小了;

    2024年02月16日
    浏览(35)
  • 力扣 98. 验证二叉搜索树

    题目来源:https://leetcode.cn/problems/validate-binary-search-tree/description/    C++题解1:中序遍历,递归法。获取数组,如果是递增则返回true,否则返回false。 C++题解2:中序遍历,递归法。不断更新最大值,初始化为最左最下层的节点值,按照中序遍历可以更新为上一节点的值。 C+

    2024年02月12日
    浏览(37)
  • Java算法_ 验证二叉搜索树(LeetCode_Hot100)

    题目描述: 给你一个二叉树的根节点 ,判断其是否是一个有效的二叉搜索树。root 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 获得更多?算法思路:代码文

    2024年02月12日
    浏览(39)
  • LeetCode刷题--- 验证二叉搜索树

    个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏:力扣递归算法题                    【C++】   前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的   我讲述题目会把讲解部分分为3个部分: 1、题目解析

    2024年02月04日
    浏览(50)
  • 【leetcode100-042/043】【二叉树】二叉搜索树的转换和验证

    【转换】 给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 思路: 可以说是递归板子题了。每次把数组切两半,中间

    2024年01月20日
    浏览(36)
  • ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

    二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子

    2023年04月23日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包