LeetCode百题【验证二叉搜索树】

题目描述

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

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

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

示例 1：

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

示例 2：

1
2
3

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

提示：

树中节点数目范围在[1, 10^4] 内
-2^31 <= Node.val <= 2^31 - 1

解法

递归
- 对于一个二叉树节点来说
- 它大于它的左子树的所有节点
- 它小于它右子树的所有节点
  - 也就是说当前节点的值是左子树的一个上届
    - 也就是说当前节点的值是右子树的一个下届


class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    /**
     * 对于一个二叉树节点来说，它大于它的左子树的所有节点
     * 它小于它右子树的所有节点
     * 也就是说 当前节点的值是左子树的一个上届
     * 也就是说 当前节点的值是右子树的一个下届
     * @param node 节点
     * @param lower 下限
     * @param upper 上限
     * @return
     */
    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        //比下届小，比上届大
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        //定义递归出口

        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}