输入输出为>>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])]) >>> is_bst(t1) True >>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)]) >>> is_bst(t2) False >>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])]) >>> is_bst(t3) False >>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])]) >>> is_bst(t4) True >>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])]) >>> is_bst(t5) True >>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])]) >>> is_bst(t6) True >>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)]) >>> is_bst(t7) False请写代码
时间: 2024-03-03 22:51:28 浏览: 111
以下是判断一棵二叉树是否为二叉搜索树的 Python 代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_bst(root: TreeNode) -> bool:
def dfs(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True
if not lower < node.val < upper:
return False
return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper)
return dfs(root)
```
该代码中,我们定义了一个 TreeNode 类来表示二叉树的节点。is_bst 函数接收一个二叉树的根节点作为参数,并返回一个布尔值,表示该二叉树是否为二叉搜索树。
is_bst 函数中,我们定义了一个内部函数 dfs,用来进行深度优先搜索。在搜索到每个节点时,我们都会检查该节点的值是否符合当前的范围(即是否在 lower 和 upper 之间),如果不符合,则返回 False。接着,我们继续对该节点的左子树和右子树进行搜索,但是对于左子树,我们需要将上界(即 upper)设置为该节点的值,对于右子树,我们需要将下界(即 lower)设置为该节点的值。这样可以保证左子树中的所有节点的值都小于当前节点的值,右子树中的所有节点的值都大于当前节点的值,从而满足二叉搜索树的性质。如果左子树和右子树都是二叉搜索树,则返回 True,否则返回 False。
我们可以通过创建几个二叉树来测试 is_bst 函数的正确性。例如,我们可以使用题目中给出的示例输入输出来测试该函数。
阅读全文