如何判断二叉搜索树

转载于公众号 勾勾的Java宇宙：mp.weixin.qq.com/s/bS8yCvHhD…

作者：德鲁伊

关于二叉树，面试官会给你埋哪些雷呢？下面来看一个题目检验下自己的水平。

二叉搜索树有以下特点：

• 根结点的值大于所有的左子树结点的值
• 根结点的值小于所有的右子树结点的值
• 左右子树也必须满足以上特性

现给定一棵二叉树，判断是否是二叉搜索树。

根据二叉搜索树的定义，本质上就是一个前序遍历。因此，可以利用前序遍历的思路来解决这道题。

首先我们在这棵树上进行模拟，用 INT64_MIN 表示负无穷大，INT64_MAX 表示正无穷大。

1. 我们假设根结点总是对的。如果总是对的，那么可以认为结点的值总是：处在区间(INT64_MIN, INT64_MAX) 以内。由于二叉树结点的值是 int，如果用 int64 总是可以保证一定在范围里面。

2. 根据二叉搜索树的定义，左子树总是小于根结点 5，那么左子树的范围就应该设置为(INT64_MIN, 5)。

3. 根据二叉搜索树的定久，右子树总是大于根结点 5，那么右子树的范围就应该设置为 (5, INT64_MAX)。

4. 然后再看结点 7 的左子树，范围应该是 (5, 7)。

经过运行的模拟，我们可以总结出以下特点：

• 通过原本给出的那棵二叉树，实际上能够构造出一棵“影子”区间二叉树，只不过这个二叉树上的结点是一个区间；

• 原二叉树上的值，需要掉在新二叉树的区间范围里面。

因此，解题的思路就是：

如何有效利用右边的“区间”二叉树验证左边二叉树的有效性？

当右边的“区间”二叉树不能成功构建，原二叉树就是一棵无效的二叉搜索树。

注：我们不是真的要构建“影子”二叉树，这样做的目的是方便思考。

“影子”二叉树是通过原二叉树生成的。树上结点就是不停地将区间进行拆分，比如：

(INT64_MIN, INT64_MAX) -> (INT64_MIN, 5) , (5, INT64_MAX)

(5, INT64_MAX) -> (5, 7), (7, INT64_MAX)

我们利用二叉树的前序遍历同时遍历这两棵二叉树。

注意，其中“影子”二叉树是动态生成的，并且我们也不保存其数据结构。

关于二叉树的边界，我们需要考虑一种情况：

一棵空二叉树，题目的定义采用的“小于”“大于”，当任何一个位置不满足二叉树的定义，就可以不用再遍历下去了。因此，我们要注意快速返回。

有了思路就可以写出以下核心代码。

class Solution {
    private boolean ans = true;
    private void preOrder(TreeNode root, Long l, Long r) {
        // 1. 如果为空树
        // 2. 如果已经有结点不满足BST的要求了
        if (root == null || !ans) {
            return;
        }
        // 检查当前结点是不是在影子二叉树的区间里面
        // 这里相当于在检查两棵二叉树相同位置的结点
        if (!(l < root.val && root.val < r)) {
            ans = false;
            return;
        }
        // 这里同时遍历左子树，(l, root.val)就是影子二叉树的左子结点
        preOrder(root.left, l, Long.valueOf(root.val));
        // 这里同时遍历右子树，(root.val, r)就是影子二叉树的右子结点
        preOrder(root.right, Long.valueOf(root.val), r);
    }
    public boolean isValidBST(TreeNode root) {
        ans = true;
        preOrder(root, Long.MIN_VALUE, Long.MAX_VALUE);
        return ans;
    }
}
复制代码

我们在传统经验的前序遍历基础上，进行了一点扩展，需要创建一棵“影子”二叉树才能进行前序遍历。

因此这道题的考点就是：找到隐藏的“影子”二叉树。

此外，遍历二叉树的时候，如果可以用递归，那么应该也可以用栈，或者 Morris 遍历。

转载于公众号 勾勾的Java宇宙：mp.weixin.qq.com/s/bS8yCvHhD…

作者：德鲁伊