用C++编写代码，试设计一个判别给定二叉树是否为二叉排序树的算法。

以下是用C++编写的判别给定二叉树是否为二叉排序树的算法：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL),(NULL) {}
};

bool isValidBST(TreeNode* root) {
    return isValidBST(root, LONG_MIN, LONG_MAX);
}

bool isValidBST(TreeNode* root, long long lower, long long upper) {
    if (root == NULL) {
        return true;
    }
    if (root->val <= lower || root->val >= upper) {
        return false;
    }
    return isValidBST(root->left, lower, root->val) && isValidBST(root->right, root->val, upper);
}

相关问题

C++编写程序 设计一个判别给定二叉树是否为二叉排序树的算法

在C++中编写一个判断给定二叉树是否为二叉排序树（Binary Search Tree, BST）的算法，我们需要考虑BST的基本特性：对于每个节点，其左子树的所有节点值都小于该节点，而右子树的所有节点值都大于该节点。下面是一个递归算法的例子：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isBST(TreeNode* root) {
    return helper(root, INT_MIN, INT_MAX);
}

bool helper(TreeNode* node, int min, int max) {
    if (node == nullptr) {
        return true; // 空节点视为满足条件
    }
    
    if (node->val < min || node->val > max) {
        return false; // 节点值不在指定范围内，不符合BST条件
    }

    if (!helper(node->left, min, node->val)) {
        return false; // 左子树不满足BST条件
    }

    if (!helper(node->right, node->val, max)) {
        return false; // 右子树不满足BST条件
    }

    return true;
}

这个`isBST`函数首先调用辅助函数`helper`，它检查当前节点值是否在最小值(min)到最大值(max)之间，并递归地检查左右子树是否也是有效的BST。

试设计一个判别给定二叉树是否为二叉排序树的算法

以下是判断给定二叉树是否为二叉排序树的算法：
1. 对二叉树进行中序遍历，如果始终能保持前一个值比后一个值小，则说明该二叉树是一棵二叉排序树。
2. 中序遍历时，用一个指针pre指向当前结点的前驱结点，如果pre为空，则说明当前结点是中序遍历的第一个结点，不必判断；否则，如果pre的值小于当前结点的值，则将pre指向当前结点，否则说明该二叉树不是一棵二叉排序树。

以下是判断给定二叉树是否为二叉排序树的Python代码实现：

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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.pre = None
        return self.helper(root)

    def helper(self, root):
        if not root:
            return True
        if not self.helper(root.left):
            return False
        if self.pre and self.pre.val >= root.val:
            return False
        self.pre = root
        return self.helper(root.right)