LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历

本文主要是介绍LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文详细探讨了五种二叉树中序遍历算法,包括递归、迭代、莫里斯遍历、线索二叉树和栈的迭代,评估了它们的效率和实用性。


题目描述

给定一个二叉树的根节点 root,返回它的中序遍历。

输入格式
  • root:二叉树的根节点。
输出格式
  • 返回中序遍历结果的列表。

示例

示例 1
输入: root = [1,null,2,3]
输出: [1,3,2]

方法一:递归

解题步骤
  1. 递归遍历:先遍历左子树,然后访问根节点,最后遍历右子树。
完整的规范代码
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef inorderTraversal(root):"""递归实现二叉树的中序遍历:param root: TreeNode, 二叉树的根节点:return: List[int], 中序遍历的结果"""def helper(node, res):if node:helper(node.left, res)res.append(node.val)helper(node.right, res)result = []helper(root, result)return result# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),每个节点访问一次。
  • 空间复杂度:(O(h)),递归栈的深度,其中 (h) 是树的高度。

方法二:迭代

解题步骤
  1. 使用栈:利用栈来模拟递归过程,先深入访问左子树,再访问节点,最后处理右子树。
完整的规范代码
def inorderTraversal(root):"""迭代实现二叉树的中序遍历:param root: TreeNode, 二叉树的根节点:return: List[int], 中序遍历的结果"""stack, res = [], []current = rootwhile current or stack:while current:stack.append(current)current = current.leftcurrent = stack.pop()res.append(current.val)current = current.rightreturn res# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),每个节点访问一次。
  • 空间复杂度:(O(h)),栈的最大深度等于树的高度。

方法三:莫里斯遍历 (Morris Traversal)

解题步骤
  1. 线索二叉树:利用叶子节点中的空 right 指针指向中序遍历的后继节点,从而实现空间复杂度为 (O(1)) 的遍历。
完整的规范代码
def inorderTraversal(root):"""莫里斯遍历实现二叉树的中序遍历:param root: TreeNode, 二叉树的根节点:return: List[int], 中序遍历的结果"""res, current = [], rootwhile current:if current.left:# 找到左子树的最右节点pre = current.leftwhile pre.right and pre.right != current:pre = pre.rightif not pre.right:pre.right = currentcurrent = current.leftelse:pre.right = Noneres.append(current.val)current = current.rightelse:res.append(current.val)current = current.rightreturn res# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),尽管看似复杂,但每个节点最多被处理两次(一次连接前驱,一次断开前驱)。
  • 空间复杂度:(O(1)),不使用额外空间。

方法四:线索二叉树

解题步骤

线索二叉树是一种通过链接空的左指针指向节点的前驱,空的右指针指向节点的后继来增加遍历效率的方法。对于中序遍历,可以通过构建线索二叉树来无需额外空间和递归地完成遍历。

  1. 构建线索:在构建或遍历时,把空的左指针指向中序遍历的前驱,右指针指向后继。
  2. 遍历节点:从根节点开始,一直向左下走到最左,然后使用线索向右移动。
完整的规范代码
def inorderTraversal(root):"""使用线索二叉树的方法进行中序遍历:param root: TreeNode, 二叉树的根节点:return: List[int], 中序遍历的结果"""result = []current = rootwhile current:if current.left:pre = current.leftwhile pre.right and pre.right != current:pre = pre.rightif not pre.right:pre.right = current  # 建立线索current = current.leftcontinuepre.right = None  # 断开线索result.append(current.val)current = current.rightreturn result# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),每个节点被访问至多两次。
  • 空间复杂度:(O(1)),不使用额外空间,除了输出列表。

方法五:使用栈的非递归迭代

解题步骤

这种方法使用显式栈存储将要访问的节点,模拟递归过程。

  1. 使用栈:利用显式栈存储节点来模拟递归的调用栈。
  2. 处理节点:按照中序的顺序处理每个节点,即左-根-右。
完整的规范代码
def inorderTraversal(root):"""使用栈的迭代方法进行中序遍历:param root: TreeNode, 二叉树的根节点:return: List[int], 中序遍历的结果"""stack = []result = []current = rootwhile current or stack:while current:stack.append(current)current = current.leftcurrent = stack.pop()result.append(current.val)current = current.rightreturn result# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),每个节点被访问一次。
  • 空间复杂度:(O(h)),栈的最大深度等于树的高度。

下面是五种中序遍历二叉树算法的优劣势对比表,这有助于直观地了解每种方法的特点和适用场景:

方法时间复杂度空间复杂度优势劣势
递归(O(n))(O(h))简单直观;直接符合中序遍历定义。可能导致栈溢出;递归深度受树高限制。
迭代(O(n))(O(h))避免递归导致的栈溢出。实现较为复杂;需要手动维护栈。
莫里斯遍历(O(n))(O(1))不使用额外空间;适合内存限制严格的环境。修改树的结构(临时);实现复杂,难以掌握。
线索二叉树(O(n))(O(1))通过线索化减少空间使用,无栈无递归。需要修改树的结构,实现较复杂。
栈的迭代(O(n))(O(h))易于理解和实现;不修改树的结构。需要额外的存储空间模拟调用栈。

应用示例

  • 算法设计与数据结构教育:递归和迭代方法经常用于教学,展示基本的树遍历技术。
  • 计算机图形学:中序遍历可用于场景图管理,处理具有层次结构的图形对象。
  • 编译器构建:在抽象语法树(AST)的处理中,中序遍历可以用于生成输出代码或。

这篇关于LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/958702

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、