跳至主要內容

验证二叉搜索树

BraumAce2024年8月9日hot100数据结构二叉树递归约 934 字大约 3 分钟

验证二叉搜索树

98.验证二叉搜索树

题意

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

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

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

思路一：前序遍历

由题意可知：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

使用递归前序遍历，使用递归函数 isValidBST(node, l, r) 来判断，判断以 node 为根的子树，其所有的节点是否都在 (l,r)(l, r) 的范围内，如果不在则直接返回。

在递归调用左子树时，需要把上界 r 改为 node.val，因为左子树的所有节点都要小于根节点的值，所以可以缩小比较范围；同理，右子树下界 l 也改为 node.val.

注意区间范围

我们写的递归函数，判断区间为 (l,r)(l, r)，注意是开区间，而节点的值范围在 [−231,231−1][-2^{31}, 2^{31} - 1] 之间。

本来看都是 int 类型，想当然地初始化上下界为 [Integer.MIN_VALUE, Integer.MAX_VALUE]，但是如果数据给的 root.val = 2147483647，即 231−12^{31} - 1，会导致边界问题，判断 x < right 会出错，因为 Ingeger.MAX_VALUE = 231−12^{31} - 1，两者相等，所以初始化范围还要更大些，故使用 Long 类型。

前序遍历在某些数据下不需要递归到叶子节点就能返回（比如根节点左儿子的值大于根节点的值，左儿子就不会继续往下递归了），而中序遍历和后序遍历至少要递归到一个叶子节点。从这个角度上来说，前序遍历是最快的。

代码：

class Solution {
    boolean isValidBST(TreeNode node, long left, long right) {
        if (node == null) return true;

        int x = node.val;
        return left < x && x < right
            && isValidBST(node.left, left, x)
            && isValidBST(node.right, x, right);
    }

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

思路二：中序遍历

中序遍历即层序遍历，先遍历左节点，再遍历根节点，最后遍历右子树。

根据题意可知中序遍历得到的序列一定是升序的。所以我们在遍历的时候实时检查当前节点的值是否大于前一个遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是。

中序遍历很好地利用了二叉搜索树的性质，使用到的变量最少。

代码：

class Solution {
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left) || root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }
}

思路三：后序遍历

后序遍历先遍历左右子树，最后遍历根节点，即自底向上计算子问题的过程。

需要遍历整棵树，先找到左右叶子节点，再一层层向上递归判断。

代码：

class Solution {
    long[] dfs(TreeNode node) {
        if (node == null) {
            return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        }
        long[] left = dfs(node.left);
        long[] right = dfs(node.right);
        long x = node.val;
        // 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
        if (right[0] <= x || x <= left[1]) {
            return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};
        }
        return new long[]{Math.min(left[0], x), Math.max(right[1], x)};
    }

    public boolean isValidBST(TreeNode root) {
        return dfs(root)[1] != Long.MAX_VALUE;
    }
}
主题美化