设计算法判断二叉树是否为二叉排序树

在C++中，判断一个二叉树是否为二叉排序树（BST，Binary Search Tree）可以通过递归的方式来实现。BST的特点是对于每个节点，其左子树中的所有节点值都小于该节点的值，而右子树中的所有节点值都大于该节点的值。

以下是一个简单的算法步骤：

1. 定义一个辅助函数`isValidBST`，接受三个参数：根节点、最小允许的整数（`minVal`）和最大允许的整数（`maxVal`）。如果根节点为空，说明树空或只有一个元素，符合BST条件。

2. 如果根节点不为空，检查它的值是否在`minVal`和`maxVal`之间：
- 如果不在范围内，返回`false`，因为BST的性质被破坏了。
- 如果在范围内，递归地调用`isValidBST`分别检查左子树和右子树，但更新`minVal`和`maxVal`的范围。对于左子树，`maxVal`保持不变；对于右子树，`minVal`设为当前节点值+1。

3. 如果所有的递归调用都返回`true`，则整个树是BST，返回`true`；否则返回`false`。

下面是相应的C++代码实现：

#include <iostream>

// 假设Node是一个二叉树节点，包含一个int value和两个指向左右子节点的指针
struct Node {
    int value;
    Node* left, *right;
};

bool isValidBST(Node* root, int minVal = INT_MIN, int maxVal = INT_MAX) {
    if (root == nullptr)
        return true;

    // 检查当前节点的值是否在允许范围内
    if (root->value <= minVal || root->value >= maxVal)
        return false;

    // 递归检查左右子树
    return (
        isValidBST(root->left, minVal, root->value) &&
        isValidBST(root->right, root->value + 1, maxVal)
    );
}

int main() {
    // 创建一个示例二叉树并检查是否为BST
    // ...

    // 使用isValidBST函数判断并打印结果
    bool isBST = isValidBST(treeRoot);
    std::cout << "Is the tree a BST? " << (isBST ? "Yes" : "No") << '\n';

    return 0;
}