题目描述

给一个二叉树，判断是否是二叉搜索树。

二叉搜索树的性质：
1. 根节点的值大于左子树的结点的值
2. 根节点的值小于右子树的结点的值
3. 左子树和右子树也是二叉搜索树

样例

Input:
    2
   / \
  1   3
Output: true

Input:
    5
   / \
  1   4
     / \
    3   6
Output: false

算法1

从上到下判断，在往下遍历子树的过程中，根据父节点的信息记录并更新子树的值的大小范围

1. 如果当前结点超过了当前的大小范围，则返回false
2. 否则递归遍历左子树，将左子树的最大值的范围更新为当前结点的值；递归遍历右子树，将右子树的最小值的范围更新为当前结点的值。

时间复杂度分析：O(N)，每个结点只遍历一次

Java 代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isBST(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;

        return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
    }
}