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

LeetCode98:验证二叉搜索树,这么简单的中等难度(用时击败100%)关于LeetCode98做这道题之前,我反复审题,最后确认:没错,不存在什么坑,这道题确实非常非常简单,然而却被官方定义为中等难度这一定是送分,

大家好,欢迎来到IT知识分享网。

关于LeetCode98

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

关于题目

  • 题目:98. 验证二叉搜索树
  • 描述
shell给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树 
  • 示例 1:

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

shell输入:root = [2,1,3] 输出:true 
  • 示例2:

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

shell输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。 
  • 提示:
shell树中节点数目范围在[1, 104] 内 -231 <= Node.val <= 231 - 1 

分析

  • 简单的说,此题的要求如下图所示:红色节点的值都小于100,蓝色节点的值都大于100,然后,往每个子节点上套这个规则即可

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

  • 此题有两处需要注意:
  1. 对于任意节点,它的左子树都要小于节点值,右子树必须大于节点值,不允许等于,一旦出现就返回false
  2. 节点值的范围:下限是int的最小值,上限是int的最大值
  • 只要注意以上两点,就能凭借最基础的二叉树遍历基本功解题了

解题思路

  • 还是以下图来说明
LeetCode98:验证二叉搜索树,这么简单的中等难度(用时击败100%)

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

编码

  • 完整代码如下,唯一要注意的就是默认上限是Long.MAX_VALUE,默认下限是Long.MIN_VALUE:
javaclass 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://yundeesoft.com/54604.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信