小编点评

**代码解析：** ```python class Solution: # 定义一个边界值，用于判断节点的范围 def isValidBST(self, root, min, max): # 如果根节点是空，则说明二叉搜索树为空 if root is None: return True # 检查自己 if root.val <= min or root.val >= max: return False # 检查左子树 if not self.isValidBST(root.left, min, root.val): return False # 检查右子树 if not self.isValidBST(root.right, root.val, max): return False # 返回真，如果左右子树都是有效的二叉搜索树 return True ``` **代码功能：** 1. 递归地遍历左子树和右子树，并使用边界值来限制搜索范围。 2. 检查每个节点的值是否在边界值中，如果是，则返回 `False`，表示二叉搜索树不合法。 3. 如果左右子树都是有效的二叉搜索树，则返回 `True`，表示二叉搜索树合法。 **重要提示：** * 左右子树的边界值应该设置为 `Long.MIN_VALUE` 和 `Long.MAX_VALUE`，因为 int 的最小值和最大值可能为 `int.min` 和 `int.max` 之间的最小值。 * 如果树中所有节点的值都相同，则该二叉搜索树也是有效的，因此返回 `True`。

正文

欢迎访问我的GitHub

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

关于LeetCode98

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

关于题目

• 题目：98. 验证二叉搜索树
• 描述

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

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

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

• 示例 1：
  

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

• 示例2：
  

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

• 提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

分析

• 简单的说，此题的要求如下图所示：红色节点的值都小于100，蓝色节点的值都大于100，然后，往每个子节点上套这个规则即可
  
• 此题有两处需要注意：

1. 对于任意节点，它的左子树都要小于节点值，右子树必须大于节点值，不允许等于，一旦出现就返回false
2. 节点值的范围：下限是int的最小值，上限是int的最大值

• 只要注意以上两点，就能凭借最基础的二叉树遍历基本功解题了

解题思路

• 还是以下图来说明
  
• 上图中，不论红色还是蓝色节点，都可以设置好一个范围区间，然后检查这些节点在不在区间内，这就是解题思路
• 其实就是中规中矩的前序遍历（口诀：根左右），每个节点都是先检查自己在不在规定范围内，然后再处理其左子树和右子树，在处理的时候，要重新设定范围，对左子树，要更新上限，对右子树，要更新下限
• 上图中，对红色节点的要求是小于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%
  
• 至此，解题完成，至今也没弄明白，一个二叉树遍历基本功考核，怎么就成了中级难度

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

学习路上，你不孤单，欣宸原创一路相伴...