编写算法,判断给定的二叉树是否伟二叉排序树
时间: 2024-11-18 08:27:18 浏览: 7
编写算法来判断一个给定的二叉树是否是“完全二叉树”或“满二叉树”,即每个层级都是满的,并且除了最后一个层级外,所有层级的节点都尽可能地向左靠拢。而如果是“二叉搜索树”(BST),则它还满足另一个条件:对于任意节点,其左子树中的所有节点值都小于该节点,右子树中的所有节点值都大于该节点。
以下是判断一个二叉树是否是二叉搜索树(BST)的基本算法:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isValidBST(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` 函数递归遍历树,检查当前节点的值是否在其父节点范围内并且满足BST的性质。如果树为空或当前节点在范围之外,返回True;否则继续检查左右子树。
至于判断是否是完全二叉树,可以使用类似的方式来处理,不过这里需要额外记录每一层的节点数并检查最后一层是否填充完整。这通常涉及到广度优先搜索(BFS)或深度优先搜索(DFS)以及一些额外的数据结构来辅助计算。
阅读全文