Write a function is_bst, which takes a Tree t and returns True if, and only if, t is a valid binary search tree, which means that: Each node has at most two children (a leaf is automatically a valid binary search tree). The children are valid binary search trees. For every node, the entries in that node's left child are less than or equal to the label of the node. For every node, the entries in that node's right child are greater than the label of the node.其中class Tree: def __init__(self, label, branches=[]): for b in branches: assert isinstance(b, Tree) self.label = label self.branches = list(branches) def is_leaf(self): return not self.branches def map(self, fn): self.label = fn(self.label) for b in self.branches: b.map(fn) def __contains__(self, e): if self.label == e: return True for b in self.branches: if e in b: return True return False def __repr__(self): if self.branches: branch_str = ', ' + repr(self.branches) else: branch_str = '' return 'Tree({0}{1})'.format(self.label, branch_str) def __str__(self): def print_tree(t, indent=0): tree_str = ' ' * indent + str(t.label) + "\n" for b in t.branches: tree_str += print_tree(b, indent + 1) return tree_str return print_tree(self).rstrip()

下面是 is_bst 函数的实现：

def is_bst(t):
    def is_bst_helper(t, min, max):
        if t is None:
            return True
        if t.label < min or t.label > max:
            return False
        left_bst = is_bst_helper(t.branches[0], min, t.label - 1)
        right_bst = is_bst_helper(t.branches[1], t.label + 1, max)
        return left_bst and right_bst

    return is_bst_helper(t, float('-inf'), float('inf'))

is_bst 函数使用递归来判断树 t 是否为二叉搜索树。is_bst_helper 函数是一个辅助函数，它接受三个参数：t 表示当前要判断的节点，min 表示当前节点值的下限，max 表示当前节点值的上限。如果当前节点为空，则返回 True。如果当前节点的值小于下限或大于上限，则返回 False。否则，递归检查左子树和右子树是否也是二叉搜索树，且左子树的值都小于等于当前节点的值，右子树的值都大于等于当前节点的值。最终，is_bst 函数调用 is_bst_helper 函数，并将根节点的下限和上限分别设置为负无穷和正无穷，来检查整棵树是否为二叉搜索树。