给定一棵二叉树，检查它是否是BST（二叉搜索树）

问题遇到的现象和发生背景

给定一棵二叉树，检查它是否是BST（二叉搜索树）
我们将假设在二叉搜索树中可能存在具有相同键的顶点。然后，为了使树成为 BST，必须满足以下要求：
对于每个顶点 X, 顶点左子树中的所有键 $X$在不到顶点的关键X，并且右子树中的所有键都大于或等于顶点的键X。

输入输出数据如图

输入数据格式

输入的第一行包含一个整数 n，树中的顶点数。下一行包含一个整数 m，树的根顶点处的值。在以下每一项中 n - 1 线，三个值 m, p 和 c 以空格分隔列出，指定树的任何顶点：
m 是一个整数，写入顶点的值。
p是一个整数(1<=p<=n-1) ，指定当前顶点的父节点的输入的行号（从零开始的行编号）。保证p 小于当前行号。c以取两个值“L”或“R”之一。值“L”表示当前顶点附加到左边的父顶点，“R”——在右边。
保证输入包含正确的二叉树。

输出数据格式

在一行中，如果给定的树是二叉搜索树，则打印“YES”，否则打印“NO”

我想要达到的结果

用Python编写程序，写一下注释，如果给定的树是二叉搜索树，则打印“YES”，否则打印“NO”。

使用第三方库 binarytree 非常方便，请参考：

Python 初识二叉树，新手也秒懂！（续：实战binarytree）_汉阳Hann's Home-CSDN博客 Python 初识二叉树，新手也秒懂！续集之——初步探索二叉树的第三方库 binarytree其使用环境、安装方法及二叉树的相关知识，请见：《Python 初识二叉树，新手也秒懂！》不能导入的请安装：pip install binarytree安装好了就导入库：import binarytree https://blog.csdn.net/boysoft2002/article/details/119066127

这个用上次那个 BST 代码， 加一个递归的check 函数就可以了。check 就是遍历整棵树，碰到不符合要求，返回不符合即可。

这个函数递归遍历一下即可实现，不是很难，建议自己写代码提高一下自己

完整代码实现如下：

class TreeNode:    # 定义树结构
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    
    def _input(self):    # 处理输入
        li = []
        for num in input().split(','):
            if num == 'None':
                li.append(None)
            else:
                li.append(int(num))
        return [0] + li    # 下标从 1 开始，便于接下来二叉树的构造
    
    def construct(self, li, pos):    # 根据列表 li 递归构造二叉树，pos 为 li 的索引位置
        if pos >= len(li) or li[pos] == None:
            return None
        node = TreeNode(li[pos])
        node.left = self.construct(li, 2*pos)
        node.right = self.construct(li, 2*pos+1)
        return node
    
    def judgeBST(self, root):    # 利用 BST 中序遍历递增的性质判断是否为 BST
        if not root:
            return True
        if not self.judgeBST(root.left):
            return False
        if self.pre != None and self.pre.val > root.val:
            return False
        self.pre = root
        if not self.judgeBST(root.right):
            return False
        return True
    
    def ans(self):    # 返回结果
        li = self._input()
        root = self.construct(li, 1)
        self.pre = None    # 全局遍历 self.pre，保存树的前驱结点
        return self.judgeBST(root)

print(Solution().ans())    # 调用函数，输出结果