当前位置： 面试刷题>> 验证二叉搜索树(经典算法150题)
### 题目描述
验证一个二叉树是否为二叉搜索树（Binary Search Tree, BST）。二叉搜索树是一个特殊的二叉树，其中每个节点都满足以下条件：
1. 节点的左子树只包含小于当前节点的数。
2. 节点的右子树只包含大于当前节点的数。
3. 左右子树也必须是二叉搜索树。
给定一个二叉树的根节点，请编写一个函数来验证它是否是二叉搜索树。
### 示例
以下是一个示例二叉树，我们需要验证它是否是二叉搜索树：
```
2
/ \
1 3
```
这个二叉树是二叉搜索树，因为对于根节点2，其左子树只包含小于2的数（1），右子树只包含大于2的数（3）。
### PHP 示例代码
```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 示例代码
```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 示例代码
```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 ? "是二叉搜索树" : "不是二叉搜索树");
```
这些示例展示了如何验证一个给定的二叉树是否为二叉搜索树，使用了递归和边界条件判断的方法。