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

94. 二叉树的中序遍历详解：迭代法核心逻辑与出入栈模拟

news 2025/5/15 5:57:19

中序遍历是二叉树遍历中最经典的算法之一，其核心顺序是 “左子树 → 根节点 → 右子树”。递归实现非常简单，但理解迭代法的实现却需要掌握栈的操作细节。本文将通过代码逐行解析，结合出入栈的模拟，彻底讲透迭代法的核心逻辑。

题目描述

给定一个二叉树的根节点 root，返回它的中序遍历结果。例如，输入 root = [1,null,2,3]，输出 [1,3,2]。

核心难点分析

1. 出入栈顺序

何时入栈？ 当当前节点存在左子树时，不断向左深入，将所有左节点入栈。
何时出栈？ 当左子树遍历到底（temp 为 null）时，弹出栈顶元素，处理该节点，并转向其右子树。

2. 循环的逻辑

循环条件：temp != null || !stack.isEmpty()。
- temp != null：表示仍有左子树需要探索；
- !stack.isEmpty()：表示需要回溯到之前的节点处理右子树。

3. 规律总结

“有左入左，无左入右，自底向上”：
- 有左子树时，持续向左入栈；
- 无左子树时，弹出栈顶节点，记录值，并转向右子树；
- 最终遍历顺序是从最左节点开始，自底向上处理。

解题思路分步解析

步骤 1：初始化栈和结果列表

List<Integer> res = new ArrayList<>();  // 存储遍历结果
Stack<TreeNode> stack = new Stack<>();  // 模拟递归的栈
TreeNode temp = root;                   // 当前处理节点

步骤 2：循环处理节点

while (temp != null || !stack.isEmpty()) {// 1. 有左子树：持续向左深入，节点入栈if (temp != null) {stack.push(temp);temp = temp.left;}// 2. 无左子树：弹出栈顶节点，记录值，转向右子树else {temp = stack.pop();res.add(temp.val);temp = temp.right;}
}

出入栈模拟示例

以二叉树 [1,2,3,4,5] 为例，结构如下：

    1/ \2   3/ \
4   5

中序遍历结果应为 [4,2,5,1,3]。以下是栈的变化过程：

当前 `temp`	栈内容（底→顶）	操作	结果 `res`
1	[]	压入 1，转向左子 2	[]
2	[1]	压入 2，转向左子 4	[]
4	[1,2]	压入 4，转向左子 null	[]
null	[1,2,4]	弹出 4，记录 4，转向右子 null	[4]
null	[1,2]	弹出 2，记录 2，转向右子 5	[4,2]
5	[1]	压入 5，转向左子 null	[4,2]
null	[1,5]	弹出 5，记录 5，转向右子 null	[4,2,5]
null	[1]	弹出 1，记录 1，转向右子 3	[4,2,5,1]
3	[]	压入 3，转向左子 null	[4,2,5,1]
null	[3]	弹出 3，记录 3，转向右子 null	[4,2,5,1,3]

关键知识点总结

1. 为什么用栈？

模拟递归调用栈：递归的本质是系统维护的栈，迭代法通过显式栈手动模拟这一过程。
避免栈溢出：当树深度较大时，递归可能引发栈溢出，迭代法更安全。

2. 循环条件的意义

temp != null：表示当前仍有未探索的左子树。
!stack.isEmpty()：表示需要回溯到之前的节点处理右子树。

3. 时间复杂度与空间复杂度

时间复杂度：O(n)，每个节点恰好被访问两次（入栈和出栈）。
空间复杂度：O(n)，最坏情况下栈存储所有节点。

完整代码

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode temp = root;while (temp != null || !stack.isEmpty()) {          if (temp != null) {stack.push(temp);temp = temp.left;} else {temp = stack.pop();res.add(temp.val);temp = temp.right;}}return res;}
}