算法-二叉搜索树的判断
2021/11/15 22:13:36
本文主要是介绍算法-二叉搜索树的判断,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题
给定一个二叉树,一个由二叉树节点组成的二叉树数据结构。每个二叉树节点都有一个整型值存储在名为“value”的属性中,两个子节点分别存储在名为“left”和“right”的属性中。子节点可以是二叉树节点本身,也可以是None(null)值。
**编写一个函数,返回一个表示二叉树是否为有效BST的布尔值。**当且仅当一个节点满足BST属性时,才称其为BST节点:
- 其值严格大于其左侧每个节点的值;
- 其值小于或等于其右侧每个节点的值;
- 它的两个子节点要么是BST节点本身,要么是None(null)值;
思路
思路比较简单的,就是判断每个节点是否满足二叉搜索树的性质:
- 左子节点的value值要小于其根节点的value值
- 右子节点的value值要大于其根节点的value值
思路一 : 如果是二叉搜索树,按照左根右中序遍历,则应该得到一个从小到大的排序列表,如果不满足,则不是二叉搜索树。
思路二: 遍历n个节点,判断当前节点是否满足二叉搜索树的性质,如果是左子节点,其最大值应该小于其父节点的值;如果是右子节点,其最小值应该大于其父节点的值。
实现
class BST: def __init__(self, value): self.value = value self.left = None self.right = None # O(n) time | O(d) space def validateBst(tree): return validateBstHelper(tree, float("-inf"), float("inf")) def validateBstHelper(tree, minValue, maxValue): if tree is None: return True if tree.value < minValue or tree.value >= maxValue: return False leftIsValid = validateBstHelper(tree.left, minValue, tree.value) rightIsValid = validateBstHelper(tree.right, tree.value, maxValue) return leftIsValid and rightIsValid
这篇关于算法-二叉搜索树的判断的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南