编写一个算法,判断给定的二叉树是否是二叉排序树
时间: 2024-09-23 20:11:14 浏览: 42
为了判断一个二叉树是否是二叉排序树(BST),可以采用递归的方法。BST的特点是每个节点的值都大于其左子树所有节点的值,并小于其右子树所有节点的值。
这里是一个简单的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):
def helper(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True
# 如果当前节点值小于下限或者大于上限,说明不是BST
if node.val <= lower or node.val > upper:
return False
# 递归检查左右子树
return helper(node.right, node.val, upper) and helper(node.left, lower, node.val)
return helper(root)
```
这个`is_BST`函数接收二叉树的根节点作为输入,内部有一个辅助函数`helper`,它会检查当前节点的值是否在其子节点范围之内。如果满足BST条件,返回True;否则,返回False。最后,对整个树应用该辅助函数。
阅读全文