验证二叉搜索树的三种方法：递归法、中序遍历法和递归中序遍历法

验证二叉搜索树（BST）是一个常见的前端面试题，通常要求我们判断一个二叉树是否满足二叉搜索树的性质。二叉搜索树的性质是：对于树中的每个节点，其左子树的所有节点值都小于该节点的值，其右子树的所有节点值都大于该节点的值。

方法一：递归法

我们可以通过递归的方式，利用二叉搜索树的性质来验证。具体步骤如下：

1. 定义一个递归函数，传入当前节点以及当前节点允许的最小值和最大值。
2. 如果当前节点为空，返回 true。
3. 如果当前节点的值不在允许的范围内，返回 false。
4. 递归检查左子树和右子树，更新允许的范围。

function isValidBST(root) {
    return validate(root, null, null);
}

function validate(node, min, max) {
    if (node === null) {
        return true;
    }
    if ((min !== null && node.val <= min) || (max !== null && node.val >= max)) {
        return false;
    }
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}

方法二：中序遍历法

二叉搜索树的中序遍历结果是一个递增的序列。我们可以利用这一性质来验证二叉搜索树。

1. 对树进行中序遍历，将遍历结果存储在一个数组中。
2. 检查数组是否是严格递增的。

function isValidBST(root) {
    const stack = [];
    let prev = null;
    
    while (root !== null || stack.length > 0) {
        while (root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (prev !== null && root.val <= prev) {
            return false;
        }
        prev = root.val;
        root = root.right;
    }
    return true;
}

方法三：递归中序遍历

我们也可以在不使用额外空间的情况下，通过递归中序遍历来验证二叉搜索树。

let prev = null;

function isValidBST(root) {
    prev = null;
    return inorder(root);
}

function inorder(node) {
    if (node === null) {
        return true;
    }
    if (!inorder(node.left)) {
        return false;
    }
    if (prev !== null && node.val <= prev) {
        return false;
    }
    prev = node.val;
    return inorder(node.right);
}

总结

以上三种方法都可以有效地验证二叉搜索树。递归法直观易懂，中序遍历法利用了二叉搜索树的性质，递归中序遍历法则在不使用额外空间的情况下实现了验证。根据具体场景和需求，可以选择合适的方法。

在实际开发中，理解这些算法的原理和实现方式，不仅有助于解决面试问题，也能提升我们对数据结构和算法的理解，从而编写出更高效的代码。