21. 验证二叉搜索树：判断一个二叉树是否是有效的二叉搜索树。

PangHu大约 4 分钟

要判断一个二叉树是否是有效的二叉搜索树（Binary Search Tree, BST），我们可以使用递归的方法。一个有效的二叉搜索树需要满足以下条件：

对于每个节点，它的左子树中的所有节点的值都小于该节点的值。
对于每个节点，它的右子树中的所有节点的值都大于该节点的值。
左右子树也必须是二叉搜索树。

一、递归法验证二叉搜索树

1. 思路

我们可以使用递归来验证二叉搜索树。对于每个节点，我们定义一个范围 [min, max]，表示当前节点的值必须在这个范围内。递归地验证每个子树：

对于左子树，当前节点的值将成为右边界（即 max），左子树的所有节点值必须小于这个值。
对于右子树，当前节点的值将成为左边界（即 min），右子树的所有节点值必须大于这个值。

初始时，根节点的值应在无穷小到无穷大之间。

2. 代码实现

// 定义二叉树的节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class ValidateBinarySearchTree {

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

    private static boolean isValidBST(TreeNode node, long min, long max) {
        // 空树是一个有效的二叉搜索树
        if (node == null) {
            return true;
        }

        // 当前节点的值必须在 min 和 max 之间
        if (node.val <= min || node.val >= max) {
            return false;
        }

        // 递归检查左子树和右子树
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }

    public static void main(String[] args) {
        // 创建一个示例二叉树
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        // 验证二叉树是否是有效的二叉搜索树
        boolean isValid = isValidBST(root);
        System.out.println("The binary tree is a valid BST: " + isValid);
    }
}

3. 时间复杂度和空间复杂度

时间复杂度：O(n)，其中 n 是二叉树中的节点数量。每个节点都被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用的栈深度为 h。

二、中序遍历法验证二叉搜索树

1. 思路

二叉搜索树的一个重要性质是：对树进行中序遍历得到的序列是递增的。因此，我们可以通过中序遍历来验证二叉搜索树。

使用一个变量 prev 来记录前一个节点的值。
在中序遍历的过程中，如果发现当前节点的值小于等于 prev 的值，则该树不是一个有效的二叉搜索树。

2. 代码实现

public class ValidateBinarySearchTreeInOrder {

    private static long prev = Long.MIN_VALUE;

    public static boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        // 递归检查左子树
        if (!isValidBST(root.left)) {
            return false;
        }

        // 当前节点的值必须大于前一个节点的值
        if (root.val <= prev) {
            return false;
        }
        prev = root.val;

        // 递归检查右子树
        return isValidBST(root.right);
    }

    public static void main(String[] args) {
        // 创建一个示例二叉树
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        // 验证二叉树是否是有效的二叉搜索树
        boolean isValid = isValidBST(root);
        System.out.println("The binary tree is a valid BST: " + isValid);
    }
}

3. 时间复杂度和空间复杂度

时间复杂度：O(n)，其中 n 是二叉树中的节点数量。每个节点都被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用的栈深度为 h。

三、总结

递归法：通过递归地验证每个节点的值是否在允许范围内，可以有效地判断二叉树是否是一个有效的二叉搜索树。时间复杂度为 O(n)，空间复杂度为 O(h)。
中序遍历法：利用二叉搜索树的中序遍历结果是递增序列的性质，也可以判断二叉树是否是一个有效的二叉搜索树。时间复杂度为 O(n)，空间复杂度为 O(h)。

两种方法都能正确地判断二叉树是否为二叉搜索树，可以根据实际情况选择合适的方法。中序遍历法更加直观，但递归法则更为通用和灵活。