算法题 403：验证二叉搜索树

（给算法爱好者加星标，修炼编程内功）

来源： 数据结构和算法-山大王wld

问题描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。

• 节点的右子树只包含大于当前节点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:

    2

   / \

  1   3

输出: true

示例 2:

输入:

    5

   / \

  1   4

     / \

    3   6

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。

     根节点的值为 5 ，但是其右子节点值为 4 。

递归写法

做这题之前我们首先要明白什么是二叉搜索树，就是每个节点左子树的值都比当前节点小，右子树的值都比当前节点大。所以看到这里我们最先想到的就是递归，我最先想到的是下面这种写法（注意是错误的）

1public boolean isValidBST(TreeNode root) {
2    if (root == null)
3        return true;
4    if (root.left != null && root.val <= root.left.val || root.right != null && root.val >= root.right.val)
5        return false;
6    return isValidBST(root.left) && isValidBST(root.right);
7}

如果一个结点是空的，我们默认他是有效的二叉搜索树，否则如果左节点不为空，我们要判断是否大于左节点的值，如果右节点不为空，我们还要判断小于右节点的值，然后我们再以左右两个子节点用相同的方式判断。看起来好像没什么问题，但我们好像忽略了一个每个节点的上限和下限，比如下面这棵树

注意6这个节点不光要小于15而且还要大于10，所以这里的每一个节点都是有一个范围的，上面的代码我只判断了6比15小，但没有和10进行比较，所以代码是错误的。这里我们来给每个节点添加一个范围，如果不在这个范围之内直接返回false，比如6的范围是(10,15)，很明显他不在这个范围内，所以他不是二叉搜索树。根节点的范围我们从Long.MIN_VALUE到Long.MAX_VALUE，来看下代码

 1public boolean isValidBST(TreeNode root) {
 2    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
 3}
 4
 5public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
 6    if (root == null)
 7        return true;
 8    //每个节点如果超过这个范围，直接返回false
 9    if (root.val >= maxVal || root.val <= minVal)
10        return false;
11    //这里再分别以左右两个子节点分别判断，
12    //左子树范围的最小值是minVal，最大值是当前节点的值，也就是root的值，因为左子树的值要比当前节点小
13    //右子数范围的最大值是maxVal，最小值是当前节点的值，也就是root的值，因为右子树的值要比当前节点大
14    return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
15}

中序遍历递归

根据二叉搜索树的性质我们知道，中序遍历二叉搜索树，遍历的结果一定是有序的。中序遍历时，判断当前节点是否大于中序遍历的前一个节点，也就是判断是否有序，如果不大于直接返回 false。

 1//前一个结点，全局的
 2TreeNode prev;
 3
 4public boolean isValidBST(TreeNode root) {
 5    if (root == null)
 6        return true;
 7    //访问左子树
 8    if (!isValidBST(root.left))
 9        return false;
10    //访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
11    if (prev != null && prev.val >= root.val)
12        return false;
13    prev = root;
14    //访问右子树
15    if (!isValidBST(root.right))
16        return false;
17    return true;
18}

中序遍历非递归

如果对树的中序遍历比较熟悉的话，这里面也有树的中序遍历的递归和非递归两种写法。我们完全可以把上面中序遍历的递归改为非递归。

 1public boolean isValidBST(TreeNode root) {
 2    if (root == null)
 3        return true;
 4    Stack<TreeNode> stack = new Stack<>();
 5    TreeNode pre = null;
 6    while (root != null || !stack.isEmpty()) {
 7        while (root != null) {
 8            stack.push(root);
 9            root = root.left;
10        }
11        root = stack.pop();
12        if (pre != null && root.val <= pre.val)
13            return false;
14        //保存前一个访问的结点
15        pre = root;
16        root = root.right;
17    }
18    return true;
19}

总结

这题可能最容易理解的是第一种解法，我们只需要给每个节点添加一个范围，然后再分别遍历每个节点，查看是否都在指定的范围内，只要有一个不在范围内，说明不是二叉搜索树，直接返回false。后面两种写法是根据二叉搜索树中序遍历的特点来判断，因为二叉搜索树中序遍历的结果是升序的，我们就按照二叉树中序遍历的方式来遍历这棵二叉树，然后在遍历的时候顺便保存一下前一个访问的结点，判断当前节点是否大于前一个结点的值，如果不大于直接返回false。

- EOF -

推荐阅读  点击标题可跳转

觉得本文有帮助？请分享给更多人

关注「算法爱好者」加星标，修炼编程内功

好文章，我在看❤️