检查树是否为二进制搜索树时出错

检查一个树是否为二进制搜索树（Binary Search Tree, BST）是计算机科学中的一个常见问题。二进制搜索树是一种特殊的二叉树，其中每个节点的值都大于其左子树中的任何值，并且小于其右子树中的任何值。

基础概念

二叉树：每个节点最多有两个子节点的树结构。
二进制搜索树：一种特殊的二叉树，满足以下性质：
- 左子树上所有节点的值均小于它的根节点的值。
- 右子树上所有节点的值均大于它的根节点的值。
- 它的左、右子树也分别为二进制搜索树。

类型

普通二进制搜索树：基本的BST实现。
平衡二进制搜索树：如AVL树、红黑树，它们通过保持树的平衡来优化性能。

应用场景

数据库索引：快速查找和检索数据。
自动补全功能：在搜索引擎或文本编辑器中快速找到可能的单词。
排序算法：通过中序遍历可以得到有序的数据序列。

可能遇到的问题及原因

在检查树是否为BST时，可能会遇到以下问题：

递归逻辑错误：递归函数没有正确地比较节点值。
边界条件处理不当：没有正确处理空树或只有一个节点的树。
整型溢出：在比较过程中可能发生整数溢出。

解决方法

以下是一个用Python编写的检查BST的函数示例：

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

def isBST(node, min_val=float('-inf'), max_val=float('inf')):
    if not node:
        return True
    if not min_val < node.val < max_val:
        return False
    return (isBST(node.left, min_val, node.val) and
            isBST(node.right, node.val, max_val))

# 示例使用
root = TreeNode(2, TreeNode(1), TreeNode(3))
print(isBST(root))  # 应该输出 True