判断一个二叉树是否是二叉排序树的代码
时间: 2023-06-16 09:02:19 浏览: 55
判断一个二叉树是否是二叉排序树,需要满足以下条件:
1. 对于任意节点,其左子树中的所有节点的值都小于该节点的值。
2. 对于任意节点,其右子树中的所有节点的值都大于该节点的值。
3. 左子树和右子树也都是二叉排序树。
根据这个条件,可以编写以下代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
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)
```
其中,helper 函数用来递归判断当前节点是否满足二叉排序树的条件,lower 和 upper 分别代表当前节点值的下限和上限,初始值为负无穷和正无穷。如果当前节点值超出了下限或上限,说明不满足条件,返回 False。否则,递归判断左右子树是否也满足条件。最后,如果所有子树都满足条件,返回 True。