【前序、中序、后序遍历递归栈的实现】

前序、中序、后序遍历递归&栈的实现

  • 递归实现
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 栈实现
    • 前序遍历
    • 中序遍历
    • 后序遍历

特性DFS(深度优先搜索)BFS(广度优先搜索)
遍历顺序深度优先,沿着树的深度遍历,直到叶子节点再回溯。广度优先,按层次从上到下、从左到右遍历。
实现方式递归或栈队列
空间复杂度O(h),h 为树的高度(递归栈的深度)。O(w),w 为树的最大宽度(队列的大小)。
时间复杂度O(n),n 为树的节点数。O(n),n 为树的节点数。
遍历结果示例前序:1 2 4 5 3 6
中序:4 2 5 1 3 6
后序:4 5 2 6 3 1
层序:1 2 3 4 5 6
  		1/ \2   3/ \   \4   5   6

递归实现

前序遍历

根节点 -> 左子树 -> 右子树

def pre_order_traversal(root):if root is None:returnprint(root.val)  # 访问根节点pre_order_traversal(root.left)  # 递归遍历左子树pre_order_traversal(root.right)  # 递归遍历右子树

中序遍历

左子树 -> 根节点 -> 右子树

def in_order_traversal(root):if root is None:returnin_order_traversal(root.left)  # 递归遍历左子树print(root.val)  # 访问根节点in_order_traversal(root.right)  # 递归遍历右子树

后序遍历

左子树 -> 右子树 -> 根节点

def post_order_traversal(root):if root is None:returnpost_order_traversal(root.left)  # 递归遍历左子树post_order_traversal(root.right)  # 递归遍历右子树print(root.val)  # 访问根节点

栈实现

前序遍历

前序遍历的顺序是:根-> 左 -> 右 (由上往下)
栈:根压入;根弹出;右、左压入;左、右弹出;
弹出顺序为:根-> 左 -> 右

def preorder_traversal(root):if not root:return []stack, result = [root], []while stack:node = stack.pop()result.append(node.val)# 先压右子树,再压左子树,保证左子树先出栈if node.right:stack.append(node.right)if node.left:stack.append(node.left)return result

中序遍历

前序遍历的顺序是:左 -> 根-> 右 (由下往上)
栈:最左的根压入;根弹出;右压入;右弹出; (最左的根:既是左,又是根)
弹出顺序为:左 -> 根-> 右

      1/ \2   3\4(1)1/ \2   3(2)
def inorder_traversal(root):stack, result = [], []current = rootwhile current or stack:# 先遍历到最左节点while current:stack.append(current)current = current.left# 弹出栈顶元素并访问current = stack.pop()result.append(current.val)# 遍历右子树current = current.rightreturn result

后序遍历

前序遍历的顺序是:左 -> 右 -> 根 (由下往上)
栈:根压入;根弹出;左、右、压入;右、左弹出;
弹出顺序为:根 -> 右 -> 左 所以需要在反转

def postorder_traversal(root):if not root:return []stack, result = [root], []while stack:node = stack.pop()result.append(node.val)# 先压左子树,再压右子树,保证右子树先出栈if node.left:stack.append(node.left)if node.right:stack.append(node.right)# 最后反转结果,得到后序遍历return result[::-1]

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MATLAB程序转C# WPF,dll集成,混合编程

工作中遇到一个需求,有一部分算法的代码需要MATLAB来进行处理,而最后需要集成到C#中的wpf项目中去,选择灵活性更高的dll,去进行集成。(可以简单理解为:将MATLAB的函数,变为C#中类的函数成员&…

「Mac畅玩鸿蒙与硬件49」UI互动应用篇26 - 数字填色游戏

本篇教程将带你实现一个数字填色小游戏,通过简单的交互逻辑,学习如何使用鸿蒙开发组件创建趣味性强的应用。 关键词 UI互动应用数字填色动态交互逻辑判断游戏开发 一、功能说明 数字填色小游戏包含以下功能: 数字选择:用户点击…

深入理解 pytest Fixture 方法及其应用

在 Python 自动化测试领域,pytest 是当之无愧的王者。提到 pytest,不得不说它的一大核心功能——Fixture。Fixture 的强大,让复杂的测试流程变得井井有条,让测试代码更加灵活和可复用。 那么,pytest 的 Fixture 究竟是…

【AI编辑器】Cursor与DeepSeek模型的集成:提升开发效率的新选择

目录 一、为什么选择DeepSeek模型 1.1 模型参数与训练 1.2 技术创新 1、FP8格式介绍 2、FP8混合精度训练的优势 3、FP8混合精度训练的技术要点 4、FP8混合精度训练的应用与挑战 1.3 性能表现 1.4 应用与部署 1.5 争议与前景 二、注册DeepSeek账号并获取API Key 三、…

什么情况会导致JVM退出?

大家好,我是锋哥。今天分享关于【什么情况会导致JVM退出?】面试题。希望对大家有帮助; 什么情况会导致JVM退出? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 JVM(Java Virtual Machine)在不同情况下可能会退出&am…

软件工程实验-实验2 结构化分析与设计-总体设计和数据库设计

一、实验内容 1. 绘制工资支付系统的功能结构图和数据库 在系统设计阶段,要设计软件体系结构,即是确定软件系统中每个程序是由哪些模块组成的,以及这些模块相互间的关系。同时把模块组织成良好的层次系统:顶层模块通过调用它的下层…

《Rust权威指南》学习笔记(三)

泛型和trait 1.泛型可以提高代码的复用能力,泛型是具体类型或其他属性的抽象代替,可以看成是一种模版,一个占位符,编译器在编译时会将这些占位符替换成具体的类型,这个过程叫做“单态化”,所以使用泛型的…

计算机网络基础(7)中科大郑铨老师笔记

应用层 目标:  网络应用的 原理:网络应用协议的概念和实现方面 传输层的服务模型 客户-服务器模式 对等模式(peerto-peer) 内容分发网络  网络应用的 实例:互联网流行的应用层协 议  HTTP  FTP  SMTP / POP3 / IMAP  DNS…

2022浙江大学信号与系统笔记

原视频地址:2022浙江大学信号与系统(含配套课件和代码) - 胡浩基老师-哔哩哔哩 ⭐⭐⭐ 我的笔记:飞书链接 - 信号与系统 基于视频,记得笔记,加了点自己的补充(有的是问 ChatGPT 的)…

数学建模入门——建模流程

摘要:本文介绍了数学建模的一般流程概述。 目录 一、前言 二、数据预处理 三、描述性统计分析 四、模型建立 五、模型评价 一、前言 本文将为想要入门数学建模的同学讲述数学建模的一般流程。但数学建模流程并非一成不变。虽有大致步骤,像分析问题、…

如何使用OpenCV进行抓图-多线程

前言 需求: 1、如何使用OpenCV捕抓Windows电脑上USB摄像头的流、 2、采用多线程 3、获知当前摄像头的帧率。 这个需求,之前就有做了,但是由于出现了一个问题,人家摄像头的帧率目前都可以达到60帧/s 了,而我的程序…

NLP CH3复习

CH3 3.1 几种损失函数 3.2 激活函数性质 3.3 哪几种激活函数会发生梯度消失 3.4 为什么会梯度消失 3.5 如何解决梯度消失和过拟合 3.6 梯度下降的区别 3.6.1 梯度下降(GD) 全批量:在每次迭代中使用全部数据来计算损失函数的梯度。计算成本…

01 数据分析介绍及工具准备

数据分析介绍及工具准备 一、工具准备二、下载和使用Anaconda三、jupyter notebook常用快捷键 一、工具准备 数据科学库 NumPy,SciPy,Pandas,Scikit-Learn 数据可视化库 Matplotlib,Seaborn 编译器 Jupyter Notebook 数据科…

机组的概述

计算机系统组成 硬件系统和软件系统 计算机硬件 1.冯诺依曼机基本思想 特点 1.采用“存储程序”工作方式 2.硬件系统由运算器,存储器,控制器,输入输出设备组成 3.指令和数据存在存储器中,形式无区别 4.指令和数据用二进制代…

Windows应用开发-解析MP4视频文件(第1部分)

下载本应用 本Windows应用解析MP4视频文件,以表格的方式显示MP4文件结构。并可以将结果保存到bmp图片。 使用方法 选择“打开MP4视频文件”菜单项,打开MP4文件,就可以获得如下图像: box的每一项,用3个矩形表示&…

Scala_【4】流程控制

第四章 分支控制if-else单分支双分支多分支返回值嵌套分支 For循环控制包含边界不包含边界循环守卫循环步长嵌套循环循环返回值 While循环Break友情链接 分支控制if-else 单分支 双分支 多分支 返回值 嵌套分支 For循环控制 Scala也为for循环这一常见的控制结构提供了非常多的…

电商Google广告:2025年提升转化率的5种策略

展望 2025 年,Google 广告领域将迎来一系列显著变化,这些趋势对于提升广告转化率至关重要,值得我们提前关注与布局。 智能化程度持续加深,用户搜索习惯愈发精细,广告格式推陈出新,视频广告势头正猛...那么…

一文大白话讲清楚TCP连接的三次握手和断开连接的四次挥手的原理

文章目录 一文大白话讲清楚TCP连接的三次握手和断开连接的四次挥手的原理1.TCP建立连接需要3次握手1.1 先讲个你兄弟的故事1.2 TCP 3次握手1.2 TCP 3次握手8件事1.3 TCP握手能不能是两次 2. TCP 断开连接要4次挥手2.1 还回到你兄弟的故事上2.2 TCP 4次挥手2.2 TCP4次挥手4件事2…

基于springboot的课程作业管理系统(源码+数据库+文档)

亲测完美运行带论文:文末获取源码 文章目录 项目简介(论文摘要)运行视频包含的文件列表(含论文)前端运行截图后端运行截图 项目简介(论文摘要) 随着科学技术的飞速发展,社会的方方面…

【ArcGIS微课1000例】0136:制作千层饼(DEM、影像、等高线、山体阴影图层)

文章目录 一、效果展示二、数据准备三、制作过程1. 打开软件2. 制作DEM图层3. 制作影像层4. 制作TIN层5. 制作等高线层四、注意事项一、效果展示 二、数据准备 订阅专栏后,从专栏配套案例数据包中的0136.rar中获取。 1. dem 2. 影像 3. 等高线 4. tin 三、制作过程 1. 打开软…