甘南藏族自治州网站建设_网站建设公司_色彩搭配_seo优化

Java版LeetCode热题100之二叉树的中序遍历：从递归到Morris遍历的深度解析

本文将全面、深入地剖析 LeetCode 第94题「二叉树的中序遍历」，不仅提供三种主流解法（递归、迭代、Morris），还涵盖算法原理、复杂度分析、面试技巧、实际应用场景以及相关题目拓展。全文约9500字，适合准备面试、夯实基础或进阶学习的开发者阅读。

一、原题回顾

题目编号：LeetCode 94
题目名称：Binary Tree Inorder Traversal（二叉树的中序遍历）
难度等级：Easy（但蕴含深刻思想）

题目描述

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

示例

示例 1：

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

示例 2：

输入：root = [] 输出：[]

示例 3：

输入：root = [1] 输出：[1]

约束条件

• 树中节点数目在范围[0, 100]内
• -100 <= Node.val <= 100

进阶要求

递归算法很简单，你可以通过迭代算法完成吗？

二、原题分析

什么是中序遍历？

在二叉树的遍历中，中序遍历（Inorder Traversal）是指按照以下顺序访问节点：

左子树 → 根节点 → 右子树

这一顺序具有非常重要的性质：对于一棵二叉搜索树（BST），其中序遍历的结果是一个严格递增的有序序列。这也是中序遍历在实际开发中最常见的应用场景之一。

为什么这道题重要？

虽然题目标记为“简单”，但它涵盖了：

• 递归与栈的等价性
• 手动模拟系统调用栈
• 空间复杂度优化（Morris遍历）
• 指针操作与线索化思想

可以说，掌握这道题的三种解法，就掌握了树遍历的核心思想。

三、答案构思

面对“中序遍历”问题，我们可以从三个层次思考：

1. 最直观的方式：利用递归天然符合“分治”思想，直接按“左-根-右”顺序递归。
2. 避免递归栈溢出：使用显式栈（Stack）模拟递归过程，实现迭代版本。
3. 极致空间优化：采用 Morris 遍历，在不使用额外栈空间的前提下完成遍历，空间复杂度降至 O(1)。

我们将依次实现这三种方法，并深入分析其原理与适用场景。

四、完整答案（Java实现）

方法一：递归（Recursive）

classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();inorder(root,res);returnres;}privatevoidinorder(TreeNodenode,List<Integer>res){if(node==null)return;inorder(node.left,res);// 访问左子树res.add(node.val);// 访问根节点inorder(node.right,res);// 访问右子树}}

✅优点：代码简洁，逻辑清晰，易于理解。
❌缺点：依赖系统调用栈，极端情况下（如退化为链表）可能导致栈溢出。

方法二：迭代（Iterative with Stack）

classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();Deque<TreeNode>stack=newLinkedList<>();TreeNodecurr=root;while(curr!=null||!stack.isEmpty()){// 一路向左，将路径上所有节点入栈while(curr!=null){stack.push(curr);curr=curr.left;}// 弹出栈顶（即当前子树的最左节点）curr=stack.pop();res.add(curr.val);// 转向右子树curr=curr.right;}returnres;}}

✅优点：避免递归，可控性强，适用于深度较大的树。
❌缺点：仍需 O(n) 额外空间存储栈。

方法三：Morris 中序遍历（Threaded Binary Tree）

classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();TreeNodecurr=root;while(curr!=null){if(curr.left==null){// 无左子树，直接访问当前节点并转向右子树res.add(curr.val);curr=curr.right;}else{// 找到左子树的最右节点（前驱节点）TreeNodepredecessor=curr.left;while(predecessor.right!=null&&predecessor.right!=curr){predecessor=predecessor.right;}if(predecessor.right==null){// 建立线索：让前驱指向当前节点predecessor.right=curr;curr=curr.left;// 继续遍历左子树}else{// 已建立线索，说明左子树已遍历完predecessor.right=null;// 恢复树结构res.add(curr.val);curr=curr.right;}}}returnres;}}

✅优点：空间复杂度 O(1)，无需栈或递归。
❌缺点：代码复杂，临时修改树结构（虽会恢复），面试中较少要求手写。

五、代码分析

递归解法分析

• 核心思想：函数调用栈自动保存“回溯点”。
• 每次递归调用inorder(node.left)后，系统栈会记住当前node的位置，待左子树遍历完后，继续执行res.add(node.val)和inorder(node.right)。
• 终止条件：node == null，即到达叶子节点的子节点。

迭代解法分析

• 关键技巧：“先压栈再移动”。
• 外层while控制整体流程：只要当前节点非空或栈非空，就继续。
• 内层while负责将当前路径上所有左孩子压入栈，直到最左叶子。
• 弹出后访问该节点，然后转向其右子树——右子树将成为新的“根”，重复上述过程。

📌记忆口诀：
“左到底，弹出记，右转走”

Morris 遍历分析

Morris 遍历的核心是利用空闲的右指针建立临时线索（thread），从而在不使用栈的情况下实现回溯。

关键步骤：

1. 若当前节点curr无左子树 → 直接访问，转向右。
2. 若有左子树：
   • 找到其左子树的最右节点（即中序前驱）。
   • 如果该前驱的right == null→ 建立线索predecessor.right = curr，然后进入左子树。
   • 如果predecessor.right == curr→ 说明左子树已遍历完，断开线索，访问curr，转向右。

💡为什么能保证每个节点被访问两次？
第一次：建立线索时（不访问值）
第二次：通过线索返回时（访问值并断开线索）

六、时间复杂度与空间复杂度分析

其中h为树的高度。最坏情况（退化为链表）时h = n，最好情况（完全平衡）时h = log n。

详细解释：

• 时间复杂度均为 O(n)：每个节点被访问常数次（递归/迭代1次，Morris最多2次），总操作线性。
• 空间复杂度：
  • 递归和迭代依赖栈，深度为树高h。
  • Morris 利用树本身的空指针，仅用几个变量，故 O(1)。

⚠️ 注意：虽然 Morris 空间最优，但在多线程环境或不允许修改输入的场景下不可用。

七、常见问题解答（FAQ）

Q1：为什么中序遍历对 BST 如此重要？

答：因为 BST 的定义是“左 < 根 < 右”，所以中序遍历结果必然是升序序列。可用于：

• 验证一棵树是否为 BST
• 获取 BST 的有序元素列表
• 实现 BST 的范围查询（如第 k 小元素）

Q2：迭代写法中，为什么内层 while 要一直往左走？

答：因为中序遍历必须先访问最左边的节点。通过不断将左孩子入栈，我们确保了栈顶始终是当前未访问子树中最左的节点，符合中序顺序。

Q3：Morris 遍历会不会破坏原树结构？

答：不会。虽然过程中会临时修改某些节点的right指针，但在第二次访问该节点时会立即恢复（predecessor.right = null）。遍历结束后，树结构与原始完全一致。

Q4：面试时应该优先写哪种解法？

答：

• 如果没特别要求，先写递归（展示基础能力）。
• 如果面试官说“不用递归”，则写迭代（考察栈的理解）。
• Morris 通常作为加分项，除非明确要求 O(1) 空间，否则不必主动写。

八、优化思路

1. 递归 → 尾递归优化？

Java 不支持尾递归优化，因此无法降低栈空间。但在 Scala、Erlang 等语言中可考虑。

2. 迭代 → 使用 ArrayDeque 替代 LinkedList？

ArrayDeque作为栈性能优于LinkedList（缓存友好，无节点对象开销）。可替换为：

Deque<TreeNode>stack=newArrayDeque<>();

3. Morris 遍历 → 提前判断是否需要线索？

若已知树是平衡的，递归/迭代的栈深度仅为 O(log n)，此时 Morris 的常数开销可能得不偿失。

4. 并行遍历？

中序遍历具有强顺序依赖（必须先左后根再右），难以并行化。但若只需收集所有节点值（不要求顺序），可用 BFS 并行处理。

九、数据结构与算法基础知识点回顾

1. 二叉树的三种 DFS 遍历

2. 递归与栈的关系

• 递归本质是系统维护的隐式栈。
• 任何递归算法都可转化为迭代 + 显式栈。
• 栈中存储的是“待完成的任务”（如：访问根、遍历右子树）。

3. 线索二叉树（Threaded Binary Tree）

• 利用空指针域存储前驱/后继信息。
• Morris 遍历是临时线索化的经典应用。
• 可实现 O(1) 空间的中序遍历，且支持双向遍历。

4. 空间复杂度 vs 辅助空间

• 总空间复杂度= 输入空间 + 辅助空间
• 本题中，输入树占 O(n)，但我们讨论的“空间复杂度”通常指额外辅助空间。
• Morris 的 O(1) 指的是辅助空间为常数，不包括输入本身。

十、面试官提问环节（模拟对话）

面试官：你写了递归解法，能说说它的空间复杂度吗？
你：最坏情况下，比如树退化成链表，递归深度为 n，所以空间复杂度是 O(n)。

面试官：如果树很大，递归可能导致栈溢出，怎么办？
你：可以改用迭代+栈的方式，手动控制栈的使用，避免系统栈溢出。

面试官：有没有办法做到 O(1) 空间？
你：有的，Morris 遍历。它通过临时修改树的指针建立线索，遍历完再恢复，空间复杂度 O(1)。

面试官：Morris 遍历的时间复杂度是多少？为什么？
你：O(n)。虽然每个节点最多被访问两次（一次建线索，一次断线索），但常数倍不影响大 O 表示法。

面试官：如果这棵树是 BST，中序遍历有什么特殊性质？
你：结果是严格递增的有序序列。这也是验证 BST 的常用方法。

面试官：能否用中序遍历解决“二叉搜索树中第 k 小的元素”？
你：可以。中序遍历到第 k 个元素即可返回，甚至可以提前终止。

十一、这道算法题在实际开发中的应用

1. 数据库索引遍历

B+ 树（数据库索引结构）的叶节点链表本质上是中序遍历的线性展开，支持高效范围查询。

2. 表达式树求值

表达式(a + b) * c可表示为二叉树，中序遍历可还原中缀表达式（需加括号处理优先级）。

3. 文件系统目录遍历

虽然通常用 BFS（层级展示），但某些工具（如tree命令）的缩进输出逻辑类似 DFS 中序。

4. 编译器语法树处理

在 AST（抽象语法树）中，中序遍历可用于生成人类可读的代码字符串。

5. 内存管理中的对象图遍历

垃圾回收器遍历对象引用图时，若需按特定顺序处理（如 finalizer），可能借鉴树遍历思想。

十二、相关题目推荐

掌握本题后，可挑战以下进阶题目：

🔥重点推荐：第 98、230、538 题，都是中序遍历在 BST 中的典型应用。

十三、总结与延伸

核心收获

1. 三种解法代表三种思维层次：

   • 递归：简洁优雅，体现分治思想
   • 迭代：手动控栈，理解系统底层
   • Morris：极致优化，展现算法创造力

2. 中序遍历 ≠ 仅仅输出节点值，它是一种访问策略，背后是“左-根-右”的处理顺序。

3. 空间换时间 or 时间换空间：Morris 用“多访问一次”换取“零额外空间”，是经典权衡。

延伸思考

• 能否统一前序、中序、后序的迭代写法？
  可以！通过在栈中记录“状态”（如 0=未处理，1=已处理左，2=已处理右），但代码复杂。

• Morris 能用于前序/后序吗？
  前序可以（访问时机不同），后序较复杂（需逆序输出），一般不推荐。

• 如果树是 N 叉树，还有中序遍历吗？
  没有标准定义。N 叉树通常只有前序和后序。

最后建议

• 面试准备：务必熟练写出递归和迭代版本。
• 工程实践：优先选择递归（可读性高），除非有栈溢出风险。
• 算法竞赛：掌握 Morris，应对 O(1) 空间限制。

结语：一道“简单”题，藏着算法世界的万千气象。从递归的优雅，到栈的掌控，再到 Morris 的巧思，每一步都是对计算机科学本质的探索。愿你在刷题路上，不止于 AC，更在于理解与创造。

欢迎点赞、收藏、评论交流！你的支持是我持续输出高质量内容的动力！