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

【LeetCode刷题日记】掌握二叉树遍历：栈实现的三种绝妙方法

news 2026/5/5 4:37:59

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

我们在前面提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

摘要：

本文介绍了使用栈实现二叉树三种遍历方式的迭代算法。
前序遍历通过"根→右→左"的入栈顺序实现；
中序遍历需要指针辅助，先一路向左压栈再处理节点；
后序遍历采用"根→右→左"顺序处理后反转结果。
三种方法对比：前序遍历访问与处理顺序一致，无需指针；中序遍历需要指针跟踪未处理节点；后序遍历通过反转前序变体实现。这些方法通过显式栈替代递归隐式栈，均能达到O(n)时间复杂度，是面试常考的二叉树遍历实现方案。

前序遍历（根 → 左 → 右）

思路
访问和处理顺序一致：先根节点 → 再左 → 再右。
用栈来模拟递归：先压右孩子，再压左孩子，这样出栈时先左后右。
步骤
根节点入栈。
循环直到栈为空：
弹出栈顶 → 处理（加入结果）。
右孩子非空 → 入栈。
左孩子非空 → 入栈。

java public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // 中 if (node.right != null) stack.push(node.right); // 右 if (node.left != null) stack.push(node.left); // 左 } return result; }

二、中序遍历（左 → 根 → 右）

为了解释清楚，我说明一下刚刚在迭代的过程中，其实我们有两个操作：
处理：将元素放进result数组中
访问：遍历节点
分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
思路
访问顺序：从根开始一直向左走到底。
处理顺序：最左的子节点先处理，然后根，然后右子树。
访问和处理顺序不一致→ 需要指针 + 栈。

步骤

指针cur指向根。
循环条件：cur != null或栈非空。
- 如果cur != null：入栈 + 往左。
- 否则（cur 为空）：
  - 弹出栈顶（处理）。
  - 指针指向右孩子。

java public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { if (cur != null) { stack.push(cur); cur = cur.left; // 左 } else { cur = stack.pop(); result.add(cur.val); // 中 cur = cur.right; // 右 } } return result; }

三、后序遍历（左 → 右 → 根）

思路
利用前序遍历的变体：
前序：根 → 左 → 右（栈：先右后左）。
变体：根 → 右 → 左（栈：先左后右）。
最后将结果反转→ 得到左 → 右 → 根。
步骤
根入栈。
循环：
弹出栈顶 → 加入结果。
先压左孩子，再压右孩子（保证出栈顺序是“根→右→左”）。
结果反转。

java public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } Collections.reverse(result); return result; }