LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)

这篇具有很好参考价值的文章主要介绍了LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

欢迎访问我的GitHub

这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos

关于LeetCode98

  • 做这道题之前,我反复审题,最后确认:没错,不存在什么坑,这道题确实非常非常简单,然而却被官方定义为中等难度
  • 这一定是送分,白捡一道中等难度题,接下来,一起来轻松愉快的享受解题过程吧

关于题目

  • 题目:98. 验证二叉搜索树
  • 描述
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

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

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树
  • 示例 1:
    LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)
输入:root = [2,1,3]
输出:true
  • 示例2:
    LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
  • 提示:
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

分析

  • 简单的说,此题的要求如下图所示:红色节点的值都小于100,蓝色节点的值都大于100,然后,往每个子节点上套这个规则即可
    LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)
  • 此题有两处需要注意:
  1. 对于任意节点,它的左子树都要小于节点值,右子树必须大于节点值,不允许等于,一旦出现就返回false
  2. 节点值的范围:下限是int的最小值,上限是int的最大值
  • 只要注意以上两点,就能凭借最基础的二叉树遍历基本功解题了

解题思路

  • 还是以下图来说明
    LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)
  • 上图中,不论红色还是蓝色节点,都可以设置好一个范围区间,然后检查这些节点在不在区间内,这就是解题思路
  • 其实就是中规中矩的前序遍历(口诀:根左右),每个节点都是先检查自己在不在规定范围内,然后再处理其左子树和右子树,在处理的时候,要重新设定范围,对左子树,要更新上限,对右子树,要更新下限
  • 上图中,对红色节点的要求是小于100,也就是说上限是100,至于下限?无所谓,那就用int的最小值-2147483648作为下限?
  • 绝对不行!!!因为:节点值可能就是int的最小值!
  • 同理,处理蓝色节点的时候,也不能用int型的最大值2147483647作为上限
  • 要用long型的最小值作为红色的下限,long型的最大值作为上限
  • 分析完成,接下来开始编码

编码

  • 完整代码如下,唯一要注意的就是默认上限是Long.MAX_VALUE,默认下限是Long.MIN_VALUE:
class Solution {
    public boolean isValidBST(TreeNode root) {

        // 左子树,只要求不能比自己大,至于小到什么程度都无所谓,所以用int最小值作为左侧边界
        if (!isValidBST(root.left, Long.MIN_VALUE, root.val)) {
            return false;
        }

        // 右子树,只要求不能比自己小,至于达到什么程度都无所谓,所以用int最大值作为右侧边界
        if (!isValidBST(root.right, root.val, Long.MAX_VALUE)) {
            return false;
        }

        return true;
    }

    public boolean isValidBST(TreeNode root, long min, long max) {
        if (null==root) {
            return true;
        }

        // 检查自己
        // 注意审题:左侧必须比自己小,不接受等于,右侧必须必自己大,不接受等于
        if (root.val<=min || root.val>=max) {
            return false;
        }

        // 左子树,只要求不能比自己大,至于小到什么程度都无所谓,所以用入参的最小值作为左侧边界
        if (!isValidBST(root.left, min, Math.min(max, root.val))) {
            return false;
        }

        // 右子树,只要求不能比自己小,至于达到什么程度都无所谓,所以用入参的最大值作为右侧边界
        if (!isValidBST(root.right, Math.max(min, root.val), max)) {
            return false;
        }

        return true;
    }
}
  • 提交,顺利AC,用时击败100%
    LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)
  • 至此,解题完成,至今也没弄明白,一个二叉树遍历基本功考核,怎么就成了中级难度

欢迎关注博客园:程序员欣宸

学习路上,你不孤单,欣宸原创一路相伴...文章来源地址https://www.toymoban.com/news/detail-707521.html

到了这里,关于LeetCode98:验证二叉搜索树,居然有这么简单的中等难度,白捡(用时击败100%)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

        一、思路 因为要验证多个节点是否是二叉搜索树,因此使用 递归 二、解题方法 设计一个递归函数 helper(root, lower, upper) 来递归判断,函数表示考虑以 root 为根的子树,判断子树中所有节点的值是否都在 (l,r)的范围内(注意是开区间)。如果 root 节点的值 val 不在 (l,r)的范

    2024年02月15日
    浏览(48)
  • 数据结构与算法之二叉树: Leetcode 98. 验证二叉搜索树 (Typescript版)

    验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree/ 描述 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身

    2024年02月16日
    浏览(40)
  • 算法训练day20Leetcode654最大二叉树617合并二叉树700二叉树中的1搜索98验证二叉搜索树

    https://leetcode.cn/problems/maximum-binary-tree/description/ 中序遍历递归,找到最大值然后作为根节点 凡是构造二叉树的题目都用前序遍历 (中左右) 为先构造中间节点,然后递归构造左子树和右子树。 确定递归函数的参数和返回值 参数传入的是存放元素的数组,返回该数组构造的二

    2024年01月21日
    浏览(42)
  • 【算法刷题day20】Leetcode:654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

    草稿图网站 java的Deque 题目: 654. 最大二叉树 解析: 代码随想录解析 解题思路 NLR的建树 代码 总结 暂无 题目: 617.合并二叉树 解析: 代码随想录解析 解题思路 如果都为root1, root2都为空,返回null;如果root1为空,root2不为空,返回root2;如果roo1不为空,root2为空,返回root

    2024年04月10日
    浏览(40)
  • 98. 验证二叉搜索树

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

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

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

    2024年02月12日
    浏览(38)
  • LeetCode_二叉搜索树_中等_236.二叉搜索树的最近公共祖先

    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉搜

    2023年04月10日
    浏览(38)
  • 【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表

    剑指 Offer 36. 二叉搜索树与双向链表 后序遍历、二叉搜索树 二叉搜索树中的任一节点的 直接前驱为其左子树的最右侧节点,直接后继为其右子树的最左侧节点 。因此,可以通过这个关系来操作原来的二叉树。 为了不影响深度较大的节点的判断,使用后序遍历。 Step1. 后序遍

    2024年02月13日
    浏览(45)
  • 【LeetCode-中等题】230. 二叉搜索树中第K小的元素

    该题最大的特点就是这个树是二叉树: 所以, 中序遍历对二叉树的遍历本身就是有序的 思想很简单,就是通过层序遍历将节点都加到List集合中,然后调用 Collections.sort(list)排序后 ,找第k小的数 list.get(k-1) 二叉树中序遍历得到的值序列是递增有序的 借助一个list集合来接收有

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

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

    2024年02月04日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包