设计一个算法判断二叉树是否为二叉排序树
时间: 2024-10-11 15:02:51 浏览: 22
写一算法,判断一棵二叉树是否是一棵二叉排序树。
设计一个算法来判断一个二叉树是否为二叉排序树(Binary Search Tree,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
# 检查当前节点是否在有效范围内
if node.val <= lower or node.val >= upper:
return False
# 递归检查左右子树
if not helper(node.right, node.val, upper):
return False
if not helper(node.left, lower, node.val):
return False
return True
return helper(root)
```
这个`is_bst`函数接受二叉树的根节点作为输入,并通过`helper`辅助函数检查每个节点的值是否满足BST的条件。如果所有节点都满足条件,返回True;反之则返回False。
阅读全文