判定树是否二叉排序树
时间: 2023-12-03 16:40:49 浏览: 71
为了判定一棵树是否为二叉排序树,需要满足以下条件:
1. 左子树上所有节点的值均小于它的根节点的值。
2. 右子树上所有节点的值均大于它的根节点的值。
3. 左右子树也分别为二叉排序树。
以下是判定树是否二叉排序树的Python代码实现:
```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()函数用于判断一棵树是否为二叉排序树。该函数使用了递归的方法,对于每个节点,判断其值是否在合法的范围内,并递归判断其左右子树是否也为二叉排序树。