作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
python源码解读
程序员必备的数学知识与应用
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

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

---

题目描述

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

输入格式

• root：二叉树的根节点。

输出格式

• 返回中序遍历结果的列表。

示例

示例 1

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

---

方法一：递归

解题步骤

1. 递归遍历：先遍历左子树，然后访问根节点，最后遍历右子树。

完整的规范代码

python">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. 使用栈：利用栈来模拟递归过程，先深入访问左子树，再访问节点，最后处理右子树。

完整的规范代码

python">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)) 的遍历。

完整的规范代码

python">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. 遍历节点：从根节点开始，一直向左下走到最左，然后使用线索向右移动。

完整的规范代码

python">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. 处理节点：按照中序的顺序处理每个节点，即左-根-右。

完整的规范代码

python">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）的处理中，中序遍历可以用于生成输出代码或。