判断二叉树是否为二叉排序树

以下是两种判断二叉树是否为二叉排序树的方法：

1.中序遍历法

对于二叉排序树来说，其中序遍历序列为一个递增有序序列。因此，我们可以对给定的二叉树进行中序遍历，如果始终能保持前一个值比后一个值小，则说明该二叉树是一棵二叉排序树。

具体实现方法如下：

def is_bst(root):
    stack = []
    pre_val = float('-inf')
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if root.val <= pre_val:
            return False
        pre_val = root.val
        root = root.right
    return True

2.递归法

根据二叉排序树的定义，对二叉树进行递归遍历，左子树关键字比根结点关键字小，右子树的关键字比根结点的关键字大，一旦有不满足条件则可判断不是二叉排序树。通过参数 flag 的值来判断，flag 为 1 表示是二叉排序树，为 0 则表示非二叉排序树，flag 初值为 1。设定全局变量 pre(初始值为 NULL)来指向遍历过程结点的前驱。

具体实现方法如下：

def is_bst(root):
    def helper(node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True
        val = node.val
        if val <= lower or val >= upper:
            return False
        if not helper(node.right, val, upper):
            return False
        if not helper(node.left, lower, val):
            return False
        return True
    return helper(root)