当前位置: 首页 > news >正文

二叉树<II>:二叉树的四种遍历方式代码实现Python3

今天我们来介绍的是二叉树的「前序」、「中序」、「后序」、「层序」四种遍历方式如何用代码实现。

还不知道这四种遍历方式原理的可以看另一篇文章:二叉树<I>:概念及二叉树的前序遍历、中序遍历、后序遍历原理

1. 相关题目

这里是 4 道相关题目:

144.二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
102. 二叉树的层序遍历

2. 题目解析

2.1 递归解法

由于层次遍历的递归解法不是主流,因此只介绍前三种的递归解法。它们的模板相对比较固定,一般都会新增一个dfs函数:

def dfs(root):if not root:returnres.append(root.val)dfs(root.left)dfs(root.right)

对于前序、中序、后序遍历只需要将res.append(root.val)放在不同位置即可,然后调用这个递归函数就可以了,代码完全一样。

2.1.1 前序遍历

class Solution:def preorderTraversal(self,root:TreeNode)->List[int]:res = []def dfs(root):# 为了让上一级定义的res能在这个函数用nonlocal resif not root:return# 拼接节点res.append(root.val)# 拼接左子树节点dfs(root.left)# 拼接右子树节点dfs(root.right)dfs(root)return res

2.1.2 中序遍历

class Solution:def inorderTraversal(self,root:TreeNode)->List[int]:res=[]def dfs(root):nonlocal res;if not root:return# 左子树dfs(root.left)res.append(root.val)# 右子树dfs(root.right)dfs(root)return res

2.1.3 后序遍历

class Solution:def afterorderTraversal(self,root:TreeNode)->List[int]:res = []def dfs(root):nonlocal resif not root:return# 左子树dfs(root.left)# 右子树dfs(root.right)res.append(root.val)dfs(root)return res

2.2 迭代解法

2.2.1 前序遍历

我们使用栈来进行迭代,过程如下:

  • 初始化栈,并将根节点入栈;
  • 当栈不为空时:弹出栈顶元素node,并将值添加到结果中;
  • 如果node的右子树非空,将右子树入栈;
  • 如果node的左子树非空,将左子树入栈。

由于栈是“先进后出”的顺序,所以入栈时先将右子树入栈,这样使得前序遍历结果为“根 -> 左 -> 右”的顺序。

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if not root:return []stack,res,cur=[],[],rootwhile cur or stack:# 进来一个节点先遍历根节点和左子树while cur:res.append(cur.val)# 进到栈里的都是根节点和左子树的点stack.append(cur)cur=cur.left# 弹出栈顶元素,走到这一步的都是把当前左子树遍历完了tmp = stack.pop()# 将弹出节点的右节点给到当前节点cur = tmp.rightreturn res

2.2.2 中序遍历

和前序遍历的代码完全相同,只是在出栈的时候才将节点tmp的值加入到结果中。

class Solution:def inorderTraversal(self,root:TreeNode)->List[int]:if not root:return []# 初始化res,stack,cur=[],[],rootwhile cur or stack:# 深入左子树,左子树节点先入栈while cur:stack.append(cur)cur = cur.left# 左子树节点先出栈temp = stack.pop()res.append(cur.val)# 深入右子树节点cur = temp.right()return res

2.2.3 后序遍历

按照上面的思想,这次我们反着思考。节点cur先到达最右端的叶子节点并将路径上的节点入栈;
然后每次从栈中弹出一个元素后,cur到达它的左节点,并将左节点看作cur继续执行上面的步骤。
最后将结果反向输出即可。

class Solution:def postorderTraversal(self,root:TreeNode)->List[int]:if not root:return []stack,res,cur=[],[],rootwhile cur or stack:# 先遍历右子树节点while cur:res.append(cur.val)stack.append(cur)cur=cur.righttemp = stack.pop()# 深入左子树节点cur = temp.leftreturn res[::-1] #反向输出

然而,后序遍历并没有按照真正的后序遍历的真实过程执行,下面对真实的过程做实现。

class Solution:def postorderTraversal(self,root:Optinal[TreeNode])->List[int]:if not root:return []res,stack = [],[root]# 为了判断父子节点关系while stack:# 取出一个节点,表示开始访问以该节点为根的子树root = stack.pop()# 如果该节点为叶子节点,或者已经访问该节点的子节点if(not root.left and not root.right) or (root.left == prev or root.right == prev):# 直接访问 res.append(root.val)prev = rootelse:# 否则就顺序把当前节点,右节点、左节点入栈stack.append(root)if root.right:stack.append(root.right)if root.left:stack.append(root.left)return res

相关文章:

二叉树<II>:二叉树的四种遍历方式代码实现Python3

今天我们来介绍的是二叉树的「前序」、「中序」、「后序」、「层序」四种遍历方式如何用代码实现。 还不知道这四种遍历方式原理的可以看另一篇文章:二叉树<I>:概念及二叉树的前序遍历、中序遍历、后序遍历原理 1. 相关题目 这…...

vite ts vue 项目提示 . Projects must list all files or use an include pattern.

vite ts vue 项目提示 . Projects must list all files or use an include pattern. 在引用一个 ts 的时候,提示如下: 需要在 tsconfig.node.json 文件中添加: {"compilerOptions": {"composite": true,"skipLibC…...

鲸鱼优化算法改进风储机组一次调频出力分配系数,以频率偏差最小为目标优化函数,结合鲸鱼算法WOA捕食过程,改进风储出力分配系数simulink与matlab联合

simulink与matlab联合 风机模糊控制 改善后的系统频率 simulink.采用风储联合数学模型...

C语言经典面试题目(七)

1、C语言中如何进行内存对齐和字节对齐? 在C语言中,内存对齐和字节对齐是为了优化内存访问速度和提高系统性能而进行的一种策略。内存对齐是指数据在内存中的存放位置必须是某个值的倍数,通常是数据类型的大小。字节对齐是指数据在内存中的存…...

2024华为春招Django面试题大全,最全知识点揭秘,面试必备!

为了帮助广大求职者更好地准备即将到来的面试,本文精心编撰了一系列涵盖InnoDB存储引擎关键知识点的面试题。这些问题不仅覆盖了InnoDB的基础知识,如其ACID特性、索引设计、锁机制等,还涵盖了性能优化、备份恢复策略等高级话题,旨…...

搜维尔科技:使用SenseGlove Nova手套操纵其“CAVE”投影室中的虚拟对象

创造了一种基于 PC 的创新型多边沉浸式环境,让参与者完全被虚拟图像和声音包围。 需要解决的挑战: 传统的 VR 系统往往缺乏真实的触摸反馈,限制了用户的沉浸感。AVR Japan 旨在通过将触觉技术融入到他们的 CAVE 系统中来应对这一挑战&#x…...

独立服务器的优势

独立服务器的优势 高性能 独立服务器提供了卓越的性能,因为它们不与其他用户共享资源。这使得您的网站或应用程序能够快速响应访问请求,并处理大量数据。 安全性 由于没有其他租户在同一服务器上,独立服务器的安全性更高。您可以更好地控制…...

前端框架vue的样式操作,以及vue提供的属性功能应用实战

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...

【自动化测试】如何在jenkins中搭建allure

相信大家在做自动化测试过程中,都会用到自动化测试环境,目前最常见的就是通过容器化方式部署自动化测试环境,但对于一些测试小白,不是很会搭建持续集成环境,特别是从0-1的过程,需要自行搭建很多依赖环境&am…...

2.域控如何强制转移操作主机角色?使用命令如何强制转移域控的操作角色?

1.实验环境介绍 实验1:模拟5种操作主机都在DC01上的域控宕机了 (1)实验先决条件 (2)测试的方向 实验2:域控夺权实验操作 方式1:AD用户和计算机工具转移操作主机角色 (1)RID角色转移: (2)PDC角色转移 (3)基础结构操作主机角色转移 方式2:powshell命令强制…...

C# event的使用

在C#中,事件(Event)是一种特殊的成员,它允许类或对象以类型安全的方式向外界发出通知,表明某个特定的行为或状态变化已经发生。 订阅该事件的其他类可以定义处理方法来响应这些通知。 事件主要基于委托机制实现&…...

外包干了9天,技术退步明显。。。。。

先说一下自己的情况,本科生,2018年我通过校招踏入了南京一家软件公司,开始了我的职业生涯。那时的我,满怀热血和憧憬,期待着在这个行业中闯出一片天地。然而,随着时间的推移,我发现自己逐渐陷入…...

Android Framework 之 Python

当然可以,我会尽量提供更详细的内容,并增加更多的例子和解释。以下是更详细的Python语言教程: Python语言教程 一、Python简介 Python是一种高级编程语言,由Guido van Rossum于1989年底发明,第一个公开发行版发行于…...

【Fitten Code】“吊打“Github Copilot的国内免费代码辅助插件

🌻个人主页:相洋同学 🥇学习在于行动、总结和坚持,共勉! 目录 1.Github Copilot 2.Fitten Code 2.1 对话体验: 2.2 代码补全体验: 2.3 Pycharm安装方法: 2.4 Vscode安装方法…...

Git中的换行符CRLF和LF问题

目录 第一章、问题分析1.1)Git报错提示1.2)报错分析 第二章、解决方式2.1)在Windows上开发并需要与Unix或macOS上的开发人员协作2.1)在Unix或macOS开发并需要与Windows上的开发人员协作2.3)不需要与其他操作系统的开发…...

go语言文件操作

标准流的操作 从标准输入中查找重复的行 // 从标准输入中查找重复的行 func main() {counts : make(map[string]int, 0)scanner : bufio.NewScanner(os.Stdin) for scanner.Scan() {counts[scanner.Text()]}for key, value : range counts {if value > 1 {fmt.Println(&quo…...

七月论文审稿GPT第3.2版和第3.5版:通过paper-review数据集分别微调Mistral、gemma

前言 我司第二项目组一直在迭代论文审稿GPT(对应的第二项目组成员除我之外,包括:阿荀、阿李、鸿飞、文弱等人),比如 七月论文审稿GPT第1版:通过3万多篇paper和10多万的review数据微调RWKV七月论文审稿GPT第2版:用一万…...

QML 自定义时间编辑控件

一.展示效果 qml自定义时间编辑控件 二.主界面调用 //main.qml import QtQuick 2.12 import QtQuick.Controls 2.5 import QtQuick.Window 2.12 import "./qml"Window {visible: truewidth: 400height: 300title: qsTr("Hello World")property date origi…...

后端程序员入门react笔记(八)-redux的使用和项目搭建

一个更好用的文档 添加链接描述 箭头函数的简化 //简化前 function countIncreAction(data) {return {type:"INCREMENT",data} } //简化后 const countIncreAction data>({type:"INCREMENT",data })react UI组件库相关资料 组件库连接和推荐 antd组…...

深度学习 精选笔记(13.2)深度卷积神经网络-AlexNet模型

学习参考: 动手学深度学习2.0Deep-Learning-with-TensorFlow-bookpytorchlightning ①如有冒犯、请联系侵删。 ②已写完的笔记文章会不定时一直修订修改(删、改、增),以达到集多方教程的精华于一文的目的。 ③非常推荐上面(学习参考&#x…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...