python多种算法对比图解实现 验证二叉树搜索树【力扣98】

简介: python多种算法对比图解实现 验证二叉树搜索树【力扣98】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

程序员必备的数学知识与应用

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给定一个二叉树的根节点 root,判断其是否是一个有效的二叉搜索树 (BST)。一个有效的 BST 定义如下:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
输入格式
  • root:二叉树的根节点。
输出格式
  • 返回布尔值,表示是否为有效的二叉搜索树。

示例

示例 1
输入: root = [2,1,3]
输出: True
解释: 给定二叉树是以下结构,显然是 BST:
    2
   / \
  1   3
示例 2
输入: root = [5,1,4,null,null,3,6]
输出: False
解释: 根节点的右子树包含比根节点小的值 (3 < 5)。

方法一:中序遍历

解题步骤
  1. 递归中序遍历:遍历树,确保遍历出的数值是递增的。
  2. 记录前一个节点值:使用一个变量记录前一个访问的节点值,比较当前节点值是否大于它。
完整的规范代码
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def isValidBST(root):
    """
    利用中序遍历验证二叉搜索树
    :param root: TreeNode, 二叉树的根节点
    :return: bool, 是否为有效的二叉搜索树
    """
    prev = None
    
    def inorder(node):
        nonlocal prev
        if not node:
            return True
        if not inorder(node.left):
            return False
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        return inorder(node.right)
    
    return inorder(root)
算法分析
  • 时间复杂度:(O(n)),需要遍历树的所有节点。
  • 空间复杂度:(O(h)),其中 (h) 是树的高度,代表递归栈的最大深度。
算法图解

对于问题 98 “验证二叉搜索树” 使用方法一中序遍历的过程,可以用 ASCII 图解来表示中序遍历的执行过程和节点值的检查。这种表示方式有助于直观地理解如何通过中序遍历确认一个树是否是二叉搜索树(BST)。中序遍历一个有效的 BST 应该产生一个递增的序列。

示例树结构

考虑一个简单的二叉树例子,以便我们可以展示中序遍历的过程:

2
   / \
  1   3

此树的中序遍历结果应该是:1, 2, 3,这是一个递增序列。

ASCII 图解

这里是二叉树的节点及其遍历的 ASCII 表示:

步骤1: 访问根节点 2
步骤2: 移至左子节点 1
步骤3: 打印左子节点 1,回到根节点 2
步骤4: 打印根节点 2,移至右子节点 3
步骤5: 打印右子节点 3

ASCII 图表解释:

2           <- 根节点开始
   / \
  1   3         <- 先访问左子树,然后根节点,最后右子树
中序遍历的步骤

通过中序遍历执行过程,我们可以追踪一个 “prev” 变量(先前访问的节点值),确保当前节点的值大于 “prev”。

中序遍历步骤:
1. 访问节点 2 的左子树(节点 1)
2. 访问节点 1,没有左子树,打印 1,记录 prev = 1
3. 返回到节点 2,prev = 1,当前节点 = 2,2 > 1 成立,打印 2,记录 prev = 2
4. 访问节点 2 的右子树(节点 3)
5. 访问节点 3,没有左子树,打印 3,记录 prev = 3
检查递增序列

每一步中,我们会检查当前节点值是否大于 “prev” 存储的值。如果这一条件在遍历过程中始终满足,那么这棵树是一个有效的二叉搜索树。

ASCII 动态展示
1 -> 2 -> 3     <- 中序遍历结果应该形成递增序列

使用 ASCII 图解来展示中序遍历的过程不仅增加了问题解决步骤的透明度,而且使得算法的验证步骤更加直观易懂,特别适合教学和解释复杂逻辑的场合。

方法二:递归验证

解题步骤
  1. 递归函数:检查每个节点是否满足左 < 当前 < 右的条件。
  2. 参数限制:使用参数 lowhigh 限制节点值的有效范围。
完整的规范代码
def isValidBST(root):
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return validate(node.left, low, node.val) and validate(node.right, node.val, high)
    
    return validate(root)
算法分析
  • 时间复杂度:(O(n)),需要遍历每个节点。
  • 空间复杂度:(O(h)),递归深度由树的高度决定。

方法三:迭代使用栈

解题步骤
  1. 使用栈:迭代地进行中序遍历。
  2. 检查顺序:确保从栈中弹出的节点值是递增的。
完整的规范代码
def isValidBST(root):
    stack, prev = [], float('-inf')
    
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if root.val <= prev:
            return False
        prev = root.val
        root = root.right
    
    return True
算法分析
  • 时间复杂度:(O(n)),每个节点访问一次。
  • 空间复杂度:(O(h)),栈的大小最多为树的高度。

不同算法的优劣势对比

特征 方法一:中序遍历 方法二:递归验证 方法三:迭代使用栈
时间复杂度 (O(n)) (O(n)) (O(n))
空间复杂度 (O(h)) (O(h)) (O(h))
优势 直观,易于理解 直接,逻辑清晰 避免递归,利于理解
劣势 依赖递归 可能过于复杂 管理栈稍复杂

应用示例

这些方法可以应用于任何需要验证二叉搜索树属性的场景,如数据库索引结构验证、自动化测试中的数据结构验证,或者作为其他算法的预处理步骤,如在进行BST相关的范围查询或平衡操作前验证其属性。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
2天前
|
存储 大数据 索引
解锁Python隐藏技能:构建高效后缀树Suffix Tree,处理大数据游刃有余!
【7月更文挑战第19天】Suffix Tree 概述:** 为高效处理字符串搜索、匹配和大数据分析,后缀树是一种优化数据结构,可快速检索后缀、执行最长公共后缀查询及字符串排序。Python中虽无内置实现,但可通过第三方库或自建代码构造。应用于字符串搜索、生物信息学等领域,提升大数据处理效率。
14 3
|
2天前
|
存储 开发者 Python
从理论到实践:Python中Trie树与Suffix Tree的完美结合,开启编程新篇章!
【7月更文挑战第19天】在编程实践中,Trie树和Suffix Tree优化了字符串处理。Trie树用于快速拼写检查,如在构建词库后,能高效判断单词是否存在。Suffix Tree则助力文本相似度检测,找寻共同子串。通过Python示例展示了Trie树插入和搜索方法,并指出Suffix Tree虽复杂但能提升性能。结合两者,实现复杂功能,展现数据结构的强大。
16 3
|
1天前
|
人工智能 算法 数据挖掘
高效文本处理新纪元:Python后缀树Suffix Tree,让数据分析更智能!
【7月更文挑战第20天】后缀树是文本处理的关键工具,它在Python中虽需第三方库支持(如pysuffixtree),但能高效执行搜索、重复内容检测等任务。应用于文本搜索、重复内容检测、生物信息学、文本压缩及智能推荐系统。随着AI和大数据发展,后缀树将在更多领域展现潜力,助力数据分析智能化和高效化。学习和利用后缀树,对于驾驭海量文本数据至关重要。**
6 1
|
1天前
|
存储 算法 Python
Python数据结构新视角:Trie树与Suffix Tree的相爱相杀,你站哪边?
【7月更文挑战第20天】在编程领域,Trie树(前缀树)与Suffix Tree(后缀树)犹如双星,各有专长。Trie树高效检索字符串集合,擅长前缀匹配,适用于自动补全和拼写检查;Suffix Tree则管理字符串所有后缀,加速子串查询,解最长公共前缀和重复子串难题。两者在不同场景发光发热,Trie树于快速响应的自动完成胜出,Suffix Tree则在基因序列分析和文本模式识别中独领风骚。抉择之间,应用场景与需求成关键,恰如剑客选剑,唯理解本质方能制胜。
|
2天前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
【7月更文挑战第19天】Trie树,又称前缀树,是优化字符串搜索的高效数据结构。通过利用公共前缀,Trie树能快速插入、删除和查找字符串。
16 2
|
11天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)回归模型(GradientBoostingRegressor算法)项目实战
Python实现GBDT(梯度提升树)回归模型(GradientBoostingRegressor算法)项目实战
|
10天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
16天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
13 3
|
15天前
|
算法 JavaScript
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
14 0
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)