Python算法题集_验证二叉搜索树

 Python算法题集_验证二叉搜索树

  • 题98:验证二叉搜索树
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【DFS递归】
    • 2) 改进版一【DFS递归+终止检测】
    • 3) 改进版二【BFS迭代+终止检测】
  • 4. 最优算法

本文为Python算法题集之一的代码示例

题98:验证二叉搜索树

1. 示例说明

  • 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

    有效 二叉搜索树定义如下:

    • 节点的左子树只包含 小于 当前节点的数。
    • 节点的右子树只包含 大于 当前节点的数。
    • 所有左子树和右子树自身必须也是二叉搜索树。

    示例 1:

    img

    输入:root = [2,1,3]
    输出:true
    

    示例 2:

    img

    输入:root = [5,1,4,null,null,3,6]
    输出:false
    解释:根节点的值是 5 ,但是右子节点的值是 4 。
    

    提示:

    • 树中节点数目范围在[1, 104]
    • -231 <= Node.val <= 231 - 1

2. 题目解析

- 题意分解

  1. 本题为二叉搜索树的验证
  2. 基本的设计思路是进行二叉树的中序遍历,基本的思路是深度优先算法【DFS(Depth-First Search)】、广度有限算法【BFS(Breadth-First Search)】
  3. 检查中序遍历的结果是否为有序的,如果有序就是二叉搜索树

- 优化思路

  1. 通常优化:减少循环层次

  2. 通常优化:增加分支,减少计算集

  3. 通常优化:采用内置算法来提升计算速度

  4. 分析题目特点,分析最优解

    1. 可以考虑采用DFS、BFS进行中序遍历

    2. 可以在过程中进行终止条件判断,减少不必要的遍历计算


- 测量工具

  • 本地化测试说明:LeetCode网站测试运行时数据波动很大,因此需要本地化测试解决这个问题
  • CheckFuncPerf(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成,详见【最优算法章节】

3. 代码展开

1) 标准求解【DFS递归】

先进行DFS递归求解,然后进行有序判断

马马虎虎,超过45%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def isValidBST_base(self, root):
     def inorderTraversal_dfs(root):
         if not root:
             return []
         return inorderTraversal_dfs(root.left) + [root.val] + inorderTraversal_dfs(root.right)
     list_node = inorderTraversal_dfs(root)
     for iIdx in range(len(list_node)-1):
         if list_node[iIdx] >= list_node[iIdx+1]:
             return False
     return True

aroot = sortedArrayToBST(nums)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.isValidBST_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 isValidBST_base 的运行时间为 317.15 ms;内存使用量为 112.00 KB 执行结果 = False

2) 改进版一【DFS递归+终止检测】

在DFS递归中进行终止检测

性能卓越,超过97%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def isValidBST_ext1(self, root):
     def inOrder(root, result):
         if root == None:
             return True
         if inOrder(root.left, result) == False:
             return False
         if result and result[-1] >= root.val:
             return False
         result.append(root.val)
         if inOrder(root.right, result) == False:
             return False
         return True
     list_node = []
     return inOrder(root, list_node)

aroot = sortedArrayToBST(nums)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.isValidBST_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 isValidBST_ext1 的运行时间为 12.99 ms;内存使用量为 8.00 KB 执行结果 = False

3) 改进版二【BFS迭代+终止检测】

采用堆栈实现BFS算法,在遍历过程中进行终止条件检测

性能优越,超过90%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def isValidBST_ext2(self, root):
     if not root:
         return True
     list_stack = []
     list_node = []
     while root or list_stack:
         if root:
             list_stack.append(root)
             root = root.left
         else:
             curnode = list_stack.pop()
             if list_node:
                 if curnode.val <= list_node[-1]:
                     return False
             list_node.append(curnode.val)
             root = curnode.right
     return True

aroot = sortedArrayToBST(nums)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.isValidBST_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 isValidBST_ext2 的运行时间为 9.97 ms;内存使用量为 568.00 KB 执行结果 = False

4. 最优算法

根据本地日志分析,最优算法为第3种方式【BFS迭代+终止检测】isValidBST_ext2

iLen = 1000000
nums = [x for x in range(iLen)]
nums[499995], nums[50005] = nums[50005], nums[499995]
def sortedArrayToBST(nums):
    if not nums:
        return
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    if mid == 0:
        return root
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    return root
aroot = sortedArrayToBST(nums)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.isValidBST_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.isValidBST_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.isValidBST_ext2, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 算法本地速度实测比较
函数 isValidBST_base 的运行时间为 317.15 ms;内存使用量为 112.00 KB 执行结果 = False
函数 isValidBST_ext1 的运行时间为 12.99 ms;内存使用量为 8.00 KB 执行结果 = False
函数 isValidBST_ext2 的运行时间为 9.97 ms;内存使用量为 568.00 KB 执行结果 = False

一日练,一日功,一日不练十日空

may the odds be ever in your favor ~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/391165.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【pyopenGL编程手册- 01/20】pyopenGL安装和简要说明

目录 一、说明二、测试系统安装的健康性三、安装64位的openGL四、写给程序员的4. 1 函数库介绍4.2 库内函数的命名 五、常见库的函数介绍5.1 OpenGL 核心库 GL5.2 OpenGL 实用库 GLU5.3 OpenGL 工具库 GLUT5.4 Windows 专用库 WGL 六、错误引发点和异常追踪6.1 错误检查开关6.…

时间序列预测模型:ARIMA模型

1. ARIMA模型原理介绍 ARIMA模型&#xff0c;全称为自回归积分滑动平均模型&#xff08;Autoregressive Integrated Moving Average Model&#xff09;&#xff0c;是一种常用的时间序列预测方法。ARIMA模型通过对时间序列数据的差分化处理&#xff0c;使非平稳时间序列数据变…

CSS之margin塌陷

margin塌陷 CSS中的外边距塌陷&#xff08;Margin Collapse&#xff09;问题是指在垂直方向上&#xff0c;当两个或多个块级元素的边距相遇时&#xff0c;它们之间的距离不是它们各自边距的总和&#xff0c;而是其中的最大值。这种现象主要出现在块级元素的上下外边距之间。 &…

【机器学习笔记】10 人工神经网络

人工神经网络发展史 1943年&#xff0c;心理学家McCulloch和逻辑学家Pitts建立神经网络的数学模型&#xff0c;MP模型 每个神经元都可以抽象为一个圆圈&#xff0c;每个圆圈都附带特定的函数称之为激活函数&#xff0c;每两个神经元之间的连接的大小的加权值即为权重。 1960年…

springboot194基于springboot的医药管理系统

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的医药管理系统 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考。 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **…

【STM32 CubeMX】串口编程DMA

文章目录 前言一、DMA方式1.1 DMA是什么1.2 CubeMX配置DMA1.3 DMA方式函数使用DMA的发送接收函数 总结 前言 在嵌入式系统中&#xff0c;串口通信是一项至关重要的功能&#xff0c;它允许单片机与外部设备进行数据交换&#xff0c;如传感器、显示器或其他设备。然而&#xff0…

C++ //练习 7.13 使用istream构造函数重写第229页的程序。

C Primer&#xff08;第5版&#xff09; 练习 7.13 练习 7.13 使用istream构造函数重写第229页的程序。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 代码块 /******************************************************************…

太阳光模拟器助力于太阳光对金属铝靶材影响

1. 引言 金属铝靶材是一种被广泛应用于薄膜制备领域的金属材料&#xff0c;具有高纯度、均一性好、结构致密等优点。其制备工艺主要包括冶金法、电化学法、物理气相沉积法等&#xff0c;其中电化学法制备的铝靶材品质最佳&#xff0c;价格也比较实惠。 其中包含&#xff1a; …

【制作100个unity游戏之25】3D背包、库存、制作、快捷栏、存储系统、砍伐树木获取资源、随机战利品宝箱2(附带项目源码)

效果演示 文章目录 效果演示系列目录前言拖放、交换物品绘制拖拽物品插槽UI修改Inventory&#xff0c;控制拖放功能 源码完结 系列目录 前言 欢迎来到【制作100个Unity游戏】系列&#xff01;本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第25篇中&#xf…

Linux桌面

系统信息的截图 登录界面右下角可以切换 Ubuntu on Wayland &#xff0c;虽然还是测试版&#xff0c;不过体验已经比之前的 Xorg 好多了&#xff0c;最笔记本上使用最影响体验的高分屏适配功能&#xff0c;在 wayland 中也是几乎完美支持的。 卸载 snap 这个 snap 是 Ubuntu …

GEO文章套路,数据下载和批次效应处理

原文链接&#xff1a; SCI文章复现 | GEO文章套路&#xff0c;数据下载和批次效应处理https://mp.weixin.qq.com/s/KBA67EJ7cCK5NDTUzrwJ2Q 一、前言 这是2024年春节后的第一个推送教程&#xff0c;我们也给大家赠送一个福利。将前期的付费教程免费推送给大家。其实&#xff…

springboot集成elk实现日志采集可视化

一、安装ELK 安装ELK组件请参考我这篇博客&#xff1a;windows下安装ELK(踩坑记录)_windows上安装elk教程-CSDN博客 这里不再重复赘述。 二、编写logstash配置 ELK组件均安装好并成功启动&#xff0c;进入到logstash组件下的config文件夹&#xff0c;创建logstash.conf配置…

网络原理-TCP/IP(7)

目录 网络层 路由选择 数据链路层 认识以太网 以太网帧格式 认识MAC地址 对比理解MAC地址和IP地址 认识MTU ARP协议 ARP协议的作用 ARP协议工作流程 重要应用层协议DNS(Domain Name System) DNS背景 NAT技术 NAT IP转换过程 NAPT NAT技术的优缺点 网络层 路由…

JDK8新增的时间

设计更合理&#xff0c;功能更丰富&#xff0c;使用更方便&#xff0c;都是不可变的对象&#xff0c;修改后会返回新的事件对象不会丢失最开始的时间&#xff0c;线程安全&#xff0c;能精确到毫秒、纳秒。 这三个类都有一个静态方法now()&#xff1a;获取系统当前时间对应的该…

Java解决下降路径最小和

Java解决下降路径最小和 01 题目 给你一个 n x n 的 方形 整数数组 matrix &#xff0c;请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始&#xff0c;并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列…

图表示学习 Graph Representation Learning chapter1 引言

图表示学习 Graph Representation Learning chapter1 引言 前言1.1图的定义1.1.1多关系图1.1.2特征信息 1.2机器学习在图中的应用1.2.1 节点分类1.2.2 关系预测1.2.3 聚类和组织检测1.2.4 图分类、回归、聚类 前言 虽然我并不研究图神经网络&#xff0c;但是我认为图高效的表示…

杂谈--spconv导出中onnx的扩展阅读

Onnx 使用 Onnx 介绍 Onnx (Open Neural Network Exchange) 的本质是一种 Protobuf 格式文件&#xff0c;通常看到的 .onnx 文件其实就是通过 Protobuf 序列化储存的文件。onnx-ml.proto 通过 protoc (Protobuf 提供的编译程序) 编译得到 onnx-ml.pb.h 和 onnx-ml.pb.cc 或 on…

创新技巧|迁移到 Google Analytics 4 时如何保存历史 Universal Analytics 数据

Google Universal Analytics 从 2023 年 7 月起停止收集数据&#xff08;除了付费 GA360 之外&#xff09;。它被Google Analytics 4取代。为此&#xff0c;不少用户疑惑&#xff1a;是否可以将累积&#xff08;历史&#xff09;数据从 Google Analytics Universal 传输到 Goog…

Python爬虫学习

1.1搭建爬虫程序开发环境 爬取未来七天天气预报 from bs4 import BeautifulSoup from bs4 import UnicodeDammit import urllib.request url"http://www.weather.com.cn/weather/101120901.shtml" try:headers{"User-Agent":"Mozilla/5.0 (Windows …

YOLOV8最强操作教程.

YoloV8详细训练教程. 相信各位都知道yolov8发布了&#xff0c;也是U神大作&#xff0c;而且V8还会出论文喔&#xff01; 2023.1.17 更新 yolov8-grad-cam热力图可视化链接 2023.1.20 更新 YOLOV8改进-添加EIoU,SIoU,AlphaIoU,FocalEIoU 链接 2023.1.30 更新 如果你需要修改或者…