二叉排序树的判定

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下两个条件：

1. 左子树上所有节点的值均小于它的根节点的值。
2. 右子树上所有节点的值均大于它的根节点的值。

因此，可以采用递归的方式判断一个二叉树是否为二叉排序树。

具体实现如下：

def is_bst(root):
    """
    判断二叉树是否为二叉排序树
    :param root: 根节点
    :return: True or False
    """
    if not root:
        return True
    # 判断左子树
    if root.left and root.left.val > root.val:
        return False
    # 判断右子树
    if root.right and root.right.val < root.val:
        return False
    # 递归判断左子树和右子树
    return is_bst(root.left) and is_bst(root.right)

其中，`root` 表示根节点，如果根节点为空，则返回 True。如果左子树不为空且左子树上某个节点的值大于根节点的值，则返回 False。同理，如果右子树不为空且右子树上某个节点的值小于根节点的值，则返回 False。最后，递归判断左子树和右子树是否都是 BST，如果都是，则返回 True，否则返回 False。

相关问题

头歌二叉排序树的判定

头歌二叉排序树（Threaded Binary Search Tree）是一种特殊的二叉排序树。在头歌二叉排序树中，每个节点除了指向其左右子树的指针外，还有指向其前驱和后继节点的线索。这些线索使得在头歌二叉排序树中进行遍历时，可以不需要使用递归或者栈来保存节点的信息，从而节省空间并提高遍历效率。

判断一棵二叉树是否为头歌二叉排序树，需要满足以下条件：
1. 对于任意一个非空节点，如果它的左子树不为空，则左子树中最右下的节点的右指针应该指向该节点；
2. 对于任意一个非空节点，如果它的右子树不为空，则右子树中最左下的节点的左指针应该指向该节点。

如果一棵二叉树满足上述两个条件，则可以将其称为头歌二叉排序树。

判定树是否二叉排序树

为了判定一棵树是否为二叉排序树，需要满足以下条件：
1. 左子树上所有节点的值均小于它的根节点的值。
2. 右子树上所有节点的值均大于它的根节点的值。
3. 左右子树也分别为二叉排序树。

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

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

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)

其中，TreeNode类表示树的节点，is_bst()函数用于判断一棵树是否为二叉排序树。该函数使用了递归的方法，对于每个节点，判断其值是否在合法的范围内，并递归判断其左右子树是否也为二叉排序树。