题目描述

验证一个二叉树是否为二叉搜索树（Binary Search Tree, BST）。二叉搜索树是一个特殊的二叉树，其中每个节点都满足以下条件：

1. 节点的左子树只包含小于当前节点的数。
2. 节点的右子树只包含大于当前节点的数。
3. 左右子树也必须是二叉搜索树。

给定一个二叉树的根节点，请编写一个函数来验证它是否是二叉搜索树。

示例

以下是一个示例二叉树，我们需要验证它是否是二叉搜索树：

    2
   / \
  1   3

这个二叉树是二叉搜索树，因为对于根节点2，其左子树只包含小于2的数（1），右子树只包含大于2的数（3）。

PHP 示例代码

class TreeNode {
    public $val;
    public $left;
    public $right;

    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function isValidBST($root, $min = null, $max = null) {
    if ($root === null) {
        return true;
    }

    if (($min !== null && $root->val <= $min) || ($max !== null && $root->val >= $max)) {
        return false;
    }

    return isValidBST($root->left, $min, $root->val) && isValidBST($root->right, $root->val, $max);
}

// 示例用法
$root = new TreeNode(2);
$root->left = new TreeNode(1);
$root->right = new TreeNode(3);

$result = isValidBST($root);
echo $result ? "是二叉搜索树" : "不是二叉搜索树";

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root, lower=float('-inf'), upper=float('inf')):
    if not root:
        return True
    if root.val <= lower or root.val >= upper:
        return False
    return (
        isValidBST(root.left, lower, root.val) and
        isValidBST(root.right, root.val, upper)
    )

# 示例用法
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

result = isValidBST(root)
print("是二叉搜索树" if result else "不是二叉搜索树")

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function isValidBST(root, min = -Infinity, max = Infinity) {
    if (!root) return true;
    if (root.val <= min || root.val >= max) return false;
    return (
        isValidBST(root.left, min, root.val) &&
        isValidBST(root.right, root.val, max)
    );
}

// 示例用法
const root = new TreeNode(2);
root.left = new TreeNode(1);
root.right = new TreeNode(3);

const result = isValidBST(root);
console.log(result ? "是二叉搜索树" : "不是二叉搜索树");

这些示例展示了如何验证一个给定的二叉树是否为二叉搜索树，使用了递归和边界条件判断的方法。