验证二叉搜索树

姊妹篇：
构建二叉搜索树 https://www.jianshu.com/p/c129df42a60f

前言

在构建二叉搜索树这篇文章中讲了二叉搜索树的性质，及如何构建一颗二叉搜索树，今天这一篇文章来验证一颗二叉树是否是二叉搜索树。

题目

//给定一个二叉树，判断其是否是一个有效的二叉搜索树。 
//
// 假设一个二叉搜索树具有如下特征： 
//
// 
// 节点的左子树只包含小于当前节点的数。 
// 节点的右子树只包含大于当前节点的数。 
// 所有左子树和右子树自身必须也是二叉搜索树。 
// 
//
// 示例 1: 
//
// 输入:
//    2
//   / \
//  1   3
//输出: true
// 
//
// 示例 2: 
//
// 输入:
//           5
//          / \
//         1   4
//        / \
//       3   6
//      / \
//     7   9
//
//
//

分析

根据二叉搜索树的满足条件，二叉搜索树的左子树上每一个点都必须小于根节点，右子树上每一个点都大于根节点。那么根据这条定义，我们可以得到

1、逐个节点遍历，记录根节点，然后和左子树的每一个节点比较，在和右子树每一个节点比较，遇到不满足的情况就返回。
2、根据二叉搜索树的性质可知，二叉搜索树的中序遍历结果应该是有序的，所以可以先把二叉搜索树的中序遍历结果输出。然后判断当前数组是否是有序数组。

上面两种方法是比较容易想到的办法，
第一种办法因为要每个点都比较，所以时间复杂度是O(n2)。
第二种办法的复杂度中序遍历是O(n),验证数组有序是OnLog(n),所以时间复杂度是O(n).

然后再次观测二叉搜索树，其实我们发现，我们没有必要和每一个点进行比较的，以这棵树为例

//           5
//          / \
//         1   4
//        / \
//       3   6
//      / \
//     7   9
//

在9这个节点的地方，如果9比1小，就可以不用再和5进行比较了，因为如果遍历到9这个位置，说明1所在节点肯定比5所在节点值要小。同理，右子树对称的地方也同样处理。

在观察，可以整理四种情况

1、左子树的左子树，取值区间在（负无穷，左子树）区间内
2、左子树的右子树，取值区间在（左子树，根节点）区间内
3、右子树的左子树，取值区间在（根节点，右子树）区间内
4、右子树的右子树，取值区间在（右子树，正无穷）区间内

这样，我们整理出了每一个节点的取值区间。

代码实现

1、判断是不是 空树
2、 判断是不是在区间范围内
3、分别判断左右子树，确定左右子树的取值区间
4、返回最终结果

class Solution {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
    }

    public static boolean isValidBST(TreeNode root) {
        // 空集也是二叉搜索树
        if (root == null) return true;
        // 左子树区间就是负无穷到根节点,右子树取值区间是根节点到正无穷
        return isValidBST(root.left, null, root.val) && isValidBST(root.right, root.val, null);
    }


    private static boolean isValidBST(TreeNode root, Integer low, Integer high) {
        // 空集也是二叉搜索树
        if (root == null) return true;
        int rootValue = root.val;

        // 判断当前节点是否在区间内
        if ((low != null && rootValue <= low) || (high != null && rootValue >= high)) {
            return false;
        }
        // 左子树区间就是父节点的下限到父节点,右子树取值区间是父节点到父节点的上限
        return isValidBST(root.left, low, rootValue) && isValidBST(root.right, rootValue, high);

    }
}