98. 验证二叉搜索树

leecode原题

题目

给你一个二叉树的根节点 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

解题思路

思路

陷阱: 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

也就是递归的过程中，左子树的最大值，右子树的最小值要不停的变更为当前跟根节点的值。

实现

源码

func isValidBST(root *TreeNode) bool {
    return check(root, math.MinInt64, math.MaxInt64)
}

func check(root *TreeNode, min, max int) bool {
    // 为空，也是有效的
    if root == nil {
        return true
    }
    if root.Val <= min || root.Val >= max {
        return false
    }
    // 这里很重要！！！！, 所有左子树的值必须小于当前根节点, 右子树的值必须大于当前根节点
    return check(root.Left, min, root.Val) && check(root.Right, root.Val, max)
}