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

二叉树前序与后序遍历迭代法详解：栈操作与顺序反转的巧妙结合

news 2025/5/15 7:00:43

二叉树的 前序遍历（根-左-右）和 后序遍历（左-右-根）是算法中的经典问题。虽然递归实现简单，但迭代法更能锻炼对栈操作的理解。本文将通过代码解析和出入栈模拟，彻底讲透这两种遍历的迭代实现，并揭示它们之间的巧妙联系。

一、前序遍历迭代法

1. 核心思路

前序遍历顺序：根节点 → 左子树 → 右子树。
迭代法核心：利用栈的 “先进后出” 特性，确保根节点先被访问，再处理左右子树。
关键操作：

根节点入栈 → 弹出根节点并记录 → 先右子节点入栈 → 再左子节点入栈。
这样，左子树会先于右子树被处理。

2. 代码逐行解析

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) {stack.push(root); // 根节点入栈}while (!stack.isEmpty()) {TreeNode node = stack.pop(); // 弹出当前节点res.add(node.val);          // 记录根节点值// 右子节点先入栈（保证左子树先处理）if (node.right != null) {stack.push(node.right);}// 左子节点后入栈（后进先出）if (node.left != null) {stack.push(node.left);}}return res;}
}

3. 出入栈模拟（以二叉树 `[1,2,3,4,5]` 为例）

      1/ \2   3/ \4   5

前序遍历结果应为 [1,2,4,5,3]。栈的变化如下：

当前栈顶节点	操作	结果 `res`	栈内容（底→顶）
1	弹出 1，右3入栈，左2入栈	[1]	[3,2]
2	弹出 2，右5入栈，左4入栈	[1,2]	[3,5,4]
4	弹出 4，无子节点	[1,2,4]	[3,5]
5	弹出 5，无子节点	[1,2,4,5]	[3]
3	弹出 3，无子节点	[1,2,4,5,3]	[]

二、后序遍历迭代法

1. 核心思路

后序遍历顺序：左子树 → 右子树 → 根节点。
迭代法核心：

逆向思维：前序遍历顺序为 根-左-右，若调整入栈顺序为 根-右-左，再将结果反转，即得到 左-右-根。
关键操作：
1. 根节点入栈 → 弹出根节点并记录 → 左子节点入栈 → 右子节点入栈。
2. 最终反转结果列表。

2. 代码逐行解析

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) {stack.push(root); // 根节点入栈}while (!stack.isEmpty()) {TreeNode node = stack.pop(); // 弹出当前节点res.add(node.val);          // 记录根节点值// 左子节点先入栈（保证右子树先处理）if (node.left != null) {stack.push(node.left);}// 右子节点后入栈（后进先出）if (node.right != null) {stack.push(node.right);}}Collections.reverse(res); // 反转结果return res;}
}

3. 出入栈模拟（以二叉树 `[1,2,3,4,5]` 为例）

后序遍历结果应为 [4,5,2,3,1]。栈的变化如下：

当前栈顶节点	操作	中间结果（未反转）	栈内容（底→顶）
1	弹出 1，左2入栈，右3入栈	[1]	[2,3]
3	弹出 3，无子节点	[1,3]	[2]
2	弹出 2，左4入栈，右5入栈	[1,3,2]	[4,5]
5	弹出 5，无子节点	[1,3,2,5]	[4]
4	弹出 4，无子节点	[1,3,2,5,4]	[]
反转结果	`[4,5,2,3,1]`

三、前序与后序遍历的关系

1. 核心规律

前序遍历顺序：根 → 左 → 右
调整后的前序顺序：根 → 右 → 左
反转结果 → 后序遍历顺序：左 → 右 → 根

2. 为什么这样可行？

调整入栈顺序后，实际遍历顺序为 根-右-左（例如 [1,3,2,5,4]）。
反转后得到 左-右-根（例如 [4,5,2,3,1]），即后序遍历结果。

四、关键知识点总结

1. 栈的作用

模拟递归调用：显式栈替代系统栈，避免递归深度过大导致的栈溢出。
控制访问顺序：通过入栈顺序调整遍历方向。

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

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

3. 前序与后序的对比

遍历方式	入栈顺序	中间结果	最终结果
前序遍历	右 → 左	根-左-右	无需反转
后序遍历	左 → 右	根-右-左	反转结果

五、完整代码

// 前序遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();res.add(node.val);if (node.right != null) stack.push(node.right);if (node.left != null) stack.push(node.left);}return res;}
}// 后序遍历
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();res.add(node.val);if (node.left != null) stack.push(node.left);if (node.right != null) stack.push(node.right);}Collections.reverse(res);return res;}
}