098.验证二叉搜索树

作者：沉默王二
发布时间：2023-11-09T15:58:52.040+0800

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

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

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

难度

中等

示例

示例 1：

输入：root=[2,1,3]

示例 2：

输入：root=[5,1,4,null,null,3,6]

解释：根节点的值是5，但是右子节点的值是4。

分析

树的本质就是递归，相信这个朴素的道理大家都能懂，二叉搜索树也不例外，我们仍然可以通过递归来检验当前二叉树是否为二叉搜索树。

观察一下题目中的条件：

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

这就把解题的思路告诉我们了：

每个节点的左子树中的最大值要小于当前节点的值
每个节点的右子树中的最小值要大于当前节点的值

也就是说，对于任意节点 n，其左子树中的所有节点的值都小于 n.val，其右子树中的所有节点的值都大于 n.val。

最后注意一个非常关键的点：空树也是二叉搜索树，这道题便能解开了。

/**

*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}/classSolution{//主方法调用辅助方法并以最大范围作为开始publicbooleanisValidBST(TreeNoderoot){returnisValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);}
//辅助递归方法publicbooleanisValidBST(TreeNoderoot,longlower,longupper){//如果到达叶子节点下的空位置，则此路径上的所有节点都满足BST条件if(root==null){returntrue;}//如果当前节点的值不在(lower,upper)的范围内，则不是BSTif(root.val<=lower||root.val>=upper){returnfalse;}//对左子树进行检查，更新上限为当前节点的值//对右子树进行检查，更新下限为当前节点的值//只有左右子树都是BST时，整棵树才是BSTreturnisValidBST(root.left,lower,root.val)&&isValidBST(root.right,root.val,upper);}}

对于最初的根节点，我们不需要对其进行任何限制，所以我们可以直接将限制设置为Long.MIN_VALUE和Long.MAX_VALUE。

假如 root 为 [5,1,4,null,null,3,6]，我们来验证一下，首先构建这棵树的结构：

14/\36

接下来，我们按照题解的过程一步步验证这是否是一个有效的二叉搜索树（BST）：

调用 isValidBST 根节点为 5，上下界为 Long.MIN_VALUE 和 Long.MAX_VALUE。
节点 5 在上下界 Long.MIN_VALUE 和 Long.MAX_VALUE 之间，因此有效。接下来：
对左子树调用 isValidBST，上界更新为 5。
对右子树调用 isValidBST，下界更新为 5。
在节点 1 上：
节点 1 在上下界 Long.MIN_VALUE 和 5 之间，因此有效。
因为节点 1 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。
在节点 4 上：
节点 4 在上下界 5 和 Long.MAX_VALUE 之间，因此有效。
对左子树调用 isValidBST，上界更新为 4。
对右子树调用 isValidBST，下界更新为 4。
在节点 3 上：
节点 3 在上下界 Long.MIN_VALUE 和 4 之间，但是节点 3 应该大于所有祖先节点中在它右边的，也就是它应该大于 5。因此，它违反了 BST 的条件，返回 false。
在节点 6 上：
尽管节点 6 在上下界 4 和 Long.MAX_VALUE 之间，但我们不会到达这里，因为它的左兄弟（节点 3）已经导致了失败的结果。

综上，当遇到节点 3 的时候，它没有满足BST的条件，所以整棵树不是BST，验证方法将返回 false。

假如 root 为 [2,1,3]，这棵树的结构如下：

按照题解的过程验证这是否是一个有效的二叉搜索树（BST）：

调用 isValidBST 根节点为 2，上下界为 Long.MIN_VALUE 和 Long.MAX_VALUE。
节点 2 在上下界 Long.MIN_VALUE 和 Long.MAX_VALUE 之间，因此有效。接下来：
对左子树调用 isValidBST，上界更新为 2。
对右子树调用 isValidBST，下界更新为 2。
在节点 1 上：
节点 1 在上下界 Long.MIN_VALUE 和 2 之间，因此有效。
节点 1 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。
在节点 3 上：
节点 3 在上下界 2 和 Long.MAX_VALUE 之间，因此有效。
节点 3 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。

由于所有节点都在各自的上下界之内，并且没有违反BST的特性，所以整棵树符合BST的定义，验证方法将返回 true。

来看一下题解效率：

为什么要用Long类型来进行限制呢？

在这个题解中，使用 Long 类型的 MIN_VALUE 和 MAX_VALUE 作为边界，是因为二叉搜索树的定义中对于任何节点来说，其左子树上的所有节点的值都要小于该节点的值，而右子树上的所有节点的值都要大于该节点的值。为了通用性，根节点的值可以是任何 Integer 类型内的值，包括 Integer.MIN_VALUE 和 Integer.MAX_VALUE。

如果我们仅使用 Integer 类型的边界来初始化，那么当根节点的值恰好是 Integer.MIN_VALUE 或 Integer.MAX_VALUE 时，我们就无法设置一个比 Integer.MIN_VALUE 更小或比 Integer.MAX_VALUE 更大的边界值了。这将导致算法不能正确地处理这些边界情况。

通过使用 Long 类型的 MIN_VALUE 和 MAX_VALUE，我们确保了即使是 Integer 范围的最小或最大值也会有有效的边界检查。这是一种编程上的预防措施，以确保算法对所有合法的 Integer 值都是健壮的。在实际情况下，对于二叉搜索树的每个节点，其值都是一个 int，但在递归检查时，我们可以用更大范围的 long 类型来避免边界条件的问题。

总结

“树的本质就是递归”，相信大家都能理解。

递归是一种通过重复将问题分解为同类的子问题而解决问题的方法。递归解决问题的过程中，我们会将问题分解为更小的子问题，然后递归地解决这些子问题，最后将它们的答案组合起来得到原始问题的答案。

在树结构中，每个节点都可以被看作是一个子树的根。树中的每个节点都重复这个结构，即它有子节点，子节点下面还有子节点，依此类推，直到叶子节点（没有子节点的节点）。这种自相似的特性是递归的本质。因此，许多在树上的操作，如搜索、插入和删除，可以自然而然地用递归来实现。

力扣链接：https://leetcode.cn/problems/validate-binary-search-tree/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

题意

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

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

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

难度

中等

示例

示例 1：

输入：root=[2,1,3]

示例 2：

输入：root=[5,1,4,null,null,3,6]

解释：根节点的值是5，但是右子节点的值是4。

分析

树的本质就是递归，相信这个朴素的道理大家都能懂，二叉搜索树也不例外，我们仍然可以通过递归来检验当前二叉树是否为二叉搜索树。

观察一下题目中的条件：

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

这就把解题的思路告诉我们了：

每个节点的左子树中的最大值要小于当前节点的值
每个节点的右子树中的最小值要大于当前节点的值

也就是说，对于任意节点 n，其左子树中的所有节点的值都小于 n.val，其右子树中的所有节点的值都大于 n.val。

最后注意一个非常关键的点：空树也是二叉搜索树，这道题便能解开了。

/**

对于最初的根节点，我们不需要对其进行任何限制，所以我们可以直接将限制设置为Long.MIN_VALUE和Long.MAX_VALUE。

假如 root 为 [5,1,4,null,null,3,6]，我们来验证一下，首先构建这棵树的结构：

14/\36

接下来，我们按照题解的过程一步步验证这是否是一个有效的二叉搜索树（BST）：

调用 isValidBST 根节点为 5，上下界为 Long.MIN_VALUE 和 Long.MAX_VALUE。
节点 5 在上下界 Long.MIN_VALUE 和 Long.MAX_VALUE 之间，因此有效。接下来：
对左子树调用 isValidBST，上界更新为 5。
对右子树调用 isValidBST，下界更新为 5。
在节点 1 上：
节点 1 在上下界 Long.MIN_VALUE 和 5 之间，因此有效。
因为节点 1 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。
在节点 4 上：
节点 4 在上下界 5 和 Long.MAX_VALUE 之间，因此有效。
对左子树调用 isValidBST，上界更新为 4。
对右子树调用 isValidBST，下界更新为 4。
在节点 3 上：
节点 3 在上下界 Long.MIN_VALUE 和 4 之间，但是节点 3 应该大于所有祖先节点中在它右边的，也就是它应该大于 5。因此，它违反了 BST 的条件，返回 false。
在节点 6 上：
尽管节点 6 在上下界 4 和 Long.MAX_VALUE 之间，但我们不会到达这里，因为它的左兄弟（节点 3）已经导致了失败的结果。

综上，当遇到节点 3 的时候，它没有满足BST的条件，所以整棵树不是BST，验证方法将返回 false。

假如 root 为 [2,1,3]，这棵树的结构如下：

按照题解的过程验证这是否是一个有效的二叉搜索树（BST）：

调用 isValidBST 根节点为 2，上下界为 Long.MIN_VALUE 和 Long.MAX_VALUE。
节点 2 在上下界 Long.MIN_VALUE 和 Long.MAX_VALUE 之间，因此有效。接下来：
对左子树调用 isValidBST，上界更新为 2。
对右子树调用 isValidBST，下界更新为 2。
在节点 1 上：
节点 1 在上下界 Long.MIN_VALUE 和 2 之间，因此有效。
节点 1 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。
在节点 3 上：
节点 3 在上下界 2 和 Long.MAX_VALUE 之间，因此有效。
节点 3 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。

由于所有节点都在各自的上下界之内，并且没有违反BST的特性，所以整棵树符合BST的定义，验证方法将返回 true。

来看一下题解效率：

为什么要用Long类型来进行限制呢？

总结

“树的本质就是递归”，相信大家都能理解。

力扣链接：https://leetcode.cn/problems/validate-binary-search-tree/

一步一个脚印

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

题意

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

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

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

难度

中等

示例

示例 1：

输入：root=[2,1,3]

示例 2：

输入：root=[5,1,4,null,null,3,6]

解释：根节点的值是5，但是右子节点的值是4。

分析

树的本质就是递归，相信这个朴素的道理大家都能懂，二叉搜索树也不例外，我们仍然可以通过递归来检验当前二叉树是否为二叉搜索树。

观察一下题目中的条件：

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

这就把解题的思路告诉我们了：

每个节点的左子树中的最大值要小于当前节点的值
每个节点的右子树中的最小值要大于当前节点的值

也就是说，对于任意节点 n，其左子树中的所有节点的值都小于 n.val，其右子树中的所有节点的值都大于 n.val。

最后注意一个非常关键的点：空树也是二叉搜索树，这道题便能解开了。

/**

对于最初的根节点，我们不需要对其进行任何限制，所以我们可以直接将限制设置为Long.MIN_VALUE和Long.MAX_VALUE。

假如 root 为 [5,1,4,null,null,3,6]，我们来验证一下，首先构建这棵树的结构：

14/\36

接下来，我们按照题解的过程一步步验证这是否是一个有效的二叉搜索树（BST）：

调用 isValidBST 根节点为 5，上下界为 Long.MIN_VALUE 和 Long.MAX_VALUE。
节点 5 在上下界 Long.MIN_VALUE 和 Long.MAX_VALUE 之间，因此有效。接下来：
对左子树调用 isValidBST，上界更新为 5。
对右子树调用 isValidBST，下界更新为 5。
在节点 1 上：
节点 1 在上下界 Long.MIN_VALUE 和 5 之间，因此有效。
因为节点 1 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。
在节点 4 上：
节点 4 在上下界 5 和 Long.MAX_VALUE 之间，因此有效。
对左子树调用 isValidBST，上界更新为 4。
对右子树调用 isValidBST，下界更新为 4。
在节点 3 上：
节点 3 在上下界 Long.MIN_VALUE 和 4 之间，但是节点 3 应该大于所有祖先节点中在它右边的，也就是它应该大于 5。因此，它违反了 BST 的条件，返回 false。
在节点 6 上：
尽管节点 6 在上下界 4 和 Long.MAX_VALUE 之间，但我们不会到达这里，因为它的左兄弟（节点 3）已经导致了失败的结果。

综上，当遇到节点 3 的时候，它没有满足BST的条件，所以整棵树不是BST，验证方法将返回 false。

假如 root 为 [2,1,3]，这棵树的结构如下：

按照题解的过程验证这是否是一个有效的二叉搜索树（BST）：

调用 isValidBST 根节点为 2，上下界为 Long.MIN_VALUE 和 Long.MAX_VALUE。
节点 2 在上下界 Long.MIN_VALUE 和 Long.MAX_VALUE 之间，因此有效。接下来：
对左子树调用 isValidBST，上界更新为 2。
对右子树调用 isValidBST，下界更新为 2。
在节点 1 上：
节点 1 在上下界 Long.MIN_VALUE 和 2 之间，因此有效。
节点 1 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。
在节点 3 上：
节点 3 在上下界 2 和 Long.MAX_VALUE 之间，因此有效。
节点 3 没有子节点，所以其左右子树都是空的，对它们的递归调用将返回 true。

由于所有节点都在各自的上下界之内，并且没有违反BST的特性，所以整棵树符合BST的定义，验证方法将返回 true。

来看一下题解效率：

为什么要用Long类型来进行限制呢？

总结

“树的本质就是递归”，相信大家都能理解。

力扣链接：https://leetcode.cn/problems/validate-binary-search-tree/

一步一个脚印

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412