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

相关文章

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代