二叉树非递归遍历：用显式栈模拟系统调用栈的艺术
2026/4/30大约 11 分钟
二叉树非递归遍历：用显式栈模拟系统调用栈的艺术
适读人群：备战面试或想深入理解递归本质的Java开发 | 阅读时长：约16分钟 | 文章类型：算法解析+多种实现对比
开篇故事
面试季，我面试了一个候选人老吴，工作六年，简历上写着"精通数据结构与算法"。
我出了一道题：二叉树的中序遍历，用非递归实现。
他想了一会儿，在白板上写出了递归版本。
我说：非递归。
他又想了一会儿，写出了一个用Stack的版本，但中序遍历只写了一半，后序遍历说"不太记得了"。
我没有难为他，因为说实话，非递归的后序遍历确实是我见过的二叉树题目里最难的。但中序遍历卡住，六年经验，这还是有点问题。
后来我们聊了一下，他说：我知道递归怎么做，但非递归总是记不住，每次都要重新想。
我说：你想过为什么非递归难记吗？因为大多数人把它当成一个需要背的"技巧"，而不是去理解它在干什么。非递归遍历本质上就是把系统递归调用时的函数调用栈，用一个显式的Deque模拟出来。你理解了这个映射关系，三种遍历的非递归版本都是同一套思路，不需要单独记。
今天我就把这个思路说透，顺带给出前中后序遍历的多种非递归实现，包括Morris遍历（O(1)空间）。
一、递归与调用栈的关系
理解非递归遍历，先要理解递归时系统做了什么。
// 递归中序遍历
void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left); // 1. 递归左子树
visit(node); // 2. 访问当前节点
inorder(node.right); // 3. 递归右子树
}当你调用inorder(root)时，系统调用栈里发生了什么：
inorder(root)入栈，暂停在第1行，把root压入函数栈帧inorder(root.left)入栈，暂停在第1行，把root.left压入栈帧- 一直往左走，直到null，开始返回
- 返回时"恢复现场"，继续执行visit，然后递归右子树
非递归的本质：用一个显式的Deque<TreeNode>，手动模拟这个入栈/出栈的过程。
二、完整的三种遍历实现
2.1 完整代码实现
package com.laozhang.tree;
import java.util.*;
/**
* 二叉树的三种非递归遍历实现
* 每种遍历都提供两种思路，帮助理解"显式栈模拟调用栈"的本质
*/
public class BinaryTreeTraversal {
// 树节点定义
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val; this.left = left; this.right = right;
}
}
// ==================== 前序遍历：根-左-右 ====================
/**
* 前序遍历：方法1（最直观）
*
* 思路：栈里存"待处理"的节点
* 每次pop一个节点，访问它，然后把右子、左子依次入栈
* （先入右子后入左子，因为栈是LIFO，左子会先被处理）
*/
public static List<Integer> preorderV1(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> stack = new ArrayDeque<>();
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;
}
/**
* 前序遍历：方法2（模拟递归调用栈，更通用的思路）
*
* 这个思路可以最自然地扩展到中序和后序
*/
public static List<Integer> preorderV2(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
// 一路向左走，同时访问（前序：先访问再递归）
while (curr != null) {
result.add(curr.val); // 访问（前序：入栈时访问）
stack.push(curr);
curr = curr.left;
}
// 回溯：弹出节点，转向右子树
curr = stack.pop();
curr = curr.right;
}
return result;
}
// ==================== 中序遍历：左-根-右 ====================
/**
* 中序遍历（最经典的非递归版本）
*
* 和前序V2的区别：访问节点的时机
* 前序：入栈时访问（curr != null时）
* 中序：出栈时访问（pop之后）
*
* 这个"入栈时 vs 出栈时"的差异，就是前/中序的本质区别
*/
public static List<Integer> inorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
// 一路向左走，只入栈，不访问
while (curr != null) {
stack.push(curr); // 入栈，但不访问
curr = curr.left;
}
// 回溯：弹出节点，访问，然后转向右子树
curr = stack.pop();
result.add(curr.val); // 出栈时访问（中序）
curr = curr.right;
}
return result;
}
// ==================== 后序遍历：左-右-根 ====================
/**
* 后序遍历：方法1（巧妙的反转思路）
*
* 后序 = 左-右-根
* 如果我们做"根-右-左"的遍历（前序的镜像），然后反转结果
* 就得到了"左-右-根"（后序）
*
* "根-右-左"的遍历：在前序V1的基础上，先入左子再入右子即可
*/
public static List<Integer> postorderV1(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>(); // 用LinkedList方便头部插入
if (root == null) return result;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.addFirst(node.val); // 头部插入 = 反转
if (node.left != null) stack.push(node.left); // 先入左（后处理→反转后先）
if (node.right != null) stack.push(node.right); // 后入右（先处理→反转后后）
}
return result;
}
/**
* 后序遍历：方法2（真正模拟递归，不用反转技巧）
*
* 这是最难理解的版本，但也是面试里最能展示功力的版本
* 关键：需要知道右子树是否已经被访问过
* 用prev记录上一个被访问的节点，通过判断来决定时机
*/
public static List<Integer> postorderV2(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
TreeNode prev = null; // 记录上一个被访问的节点
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left; // 一路向左
}
curr = stack.peek(); // 不弹出，只查看
// 判断是否可以访问curr：
// 条件：右子树为空 或 右子树已经被访问过（prev == curr.right）
if (curr.right == null || curr.right == prev) {
result.add(curr.val); // 访问
prev = curr; // 记录上一个访问的节点
stack.pop(); // 弹出
curr = null; // 不转向右子树（已经处理过了）
} else {
curr = curr.right; // 转向右子树（还没处理）
}
}
return result;
}
// ==================== Morris遍历：O(1)空间 ====================
/**
* Morris中序遍历：O(1)额外空间
*
* 核心思路：用树节点本身存储线索（临时修改叶子节点的right指针）
* 使右子树为空的节点的right指针指向中序后继，访问后再恢复
*
* 时间O(n)，空间O(1)（不使用栈或递归）
* 适合对内存极度敏感的场景
*/
public static List<Integer> morrisInorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
// 没有左子树：直接访问，移到右子树
result.add(curr.val);
curr = curr.right;
} else {
// 找到中序前驱（左子树的最右节点）
TreeNode predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 前驱的right还没指向curr：建立线索，往左走
predecessor.right = curr; // 临时线索
curr = curr.left;
} else {
// 前驱的right已经指向curr：说明左子树访问完了
predecessor.right = null; // 恢复树结构
result.add(curr.val); // 访问当前节点
curr = curr.right;
}
}
}
return result;
}
// ==================== 测试 ====================
public static void main(String[] args) {
// 构建测试树：
// 1
// / \
// 2 3
// / \ \
// 4 5 6
TreeNode root = new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, null, new TreeNode(6))
);
System.out.println("前序（V1）: " + preorderV1(root)); // [1, 2, 4, 5, 3, 6]
System.out.println("前序（V2）: " + preorderV2(root)); // [1, 2, 4, 5, 3, 6]
System.out.println("中序: " + inorder(root)); // [4, 2, 5, 1, 3, 6]
System.out.println("后序（V1）: " + postorderV1(root)); // [4, 5, 2, 6, 3, 1]
System.out.println("后序（V2）: " + postorderV2(root)); // [4, 5, 2, 6, 3, 1]
System.out.println("Morris中序: " + morrisInorder(root)); // [4, 2, 5, 1, 3, 6]
}
}2.2 层序遍历（BFS）
package com.laozhang.tree;
import java.util.*;
/**
* 层序遍历及其变种
* 层序遍历是BFS，用队列而不是栈
*/
public class LevelOrderTraversal {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val; this.left = left; this.right = right;
}
}
/**
* 基础层序遍历：所有节点在一个列表里
*/
public static List<Integer> levelOrder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
result.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return result;
}
/**
* 带层信息的层序遍历（LeetCode 102）
* 每一层的节点分别放在一个子列表里
*
* 关键技巧：每次循环前记录queue.size()，
* 这就是当前层的节点数，处理完这么多节点就进入下一层
*/
public static List<List<Integer>> levelOrderByLevel(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size(); // 当前层的节点数
List<Integer> currentLevel = new ArrayList<>(levelSize);
for (int i = 0; i < levelSize; i++) { // 只处理当前层的节点
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(currentLevel);
}
return result;
}
/**
* 实用应用：计算二叉树最大深度（非递归BFS版本）
*
* 递归版只需3行，但面试时展示BFS版更有层次感
* 据我观察：手写出BFS层序的候选人，面试通过率高很多
*/
public static int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
depth++; // 每进入新一层，深度+1
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return depth;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, null, new TreeNode(6))
);
System.out.println("层序: " + levelOrder(root));
// [1, 2, 3, 4, 5, 6]
System.out.println("分层层序: " + levelOrderByLevel(root));
// [[1], [2, 3], [4, 5, 6]]
System.out.println("最大深度: " + maxDepth(root));
// 3
}
}四、踩坑实录
坑1：后序遍历V2写法里，prev没有正确初始化
报错现象：非递归后序遍历输出结果不对，或者某些节点被重复访问。
根本原因：prev没有初始化为null，或者在循环里curr = null没有被正确设置，导致进入了错误的分支。这个版本的代码细节太多，任何一个地方出错都会导致无限循环或结果错误。
具体解法：
// 调试技巧：在关键判断处加打印
public static List<Integer> postorderDebug(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
TreeNode prev = null;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.peek();
System.out.printf("peek: %d, right: %s, prev: %s%n",
curr.val,
curr.right == null ? "null" : String.valueOf(curr.right.val),
prev == null ? "null" : String.valueOf(prev.val));
if (curr.right == null || curr.right == prev) {
result.add(curr.val);
prev = curr;
stack.pop();
curr = null; // 关键：不能忘记这行！
} else {
curr = curr.right;
}
}
return result;
}坑2：Morris遍历在途中修改了树结构，不适合并发场景
报错现象：一个读多写少的系统，用Morris遍历统计树的内容，偶发空指针异常，难以复现。
根本原因：Morris遍历会临时修改树节点的right指针（线索化），如果遍历过程中另一个线程正在读树，读到了中间状态的指针，就可能NPE或拿到错误数据。
具体解法：
// 并发场景下，不要用Morris遍历
// 改用普通非递归遍历（显式栈）+ 读写锁保护树结构
// 或者只在单线程、对内存极度敏感的场景用Morris遍历
// 比如：嵌入式系统、内存受限的设备坑3：遍历过程中修改树，结果不可预期
报错现象：在遍历树的同时，另一个线程在删除节点，遍历结果包含了已删除的节点，或者出现NPE。
根本原因：二叉树的非递归遍历（包括递归遍历）对并发修改没有任何保护。Iterator至少有fast-fail机制，但树遍历连这个都没有。
具体解法：
// 方案1：遍历前复制一份树的快照（适合小树）
// 方案2：用读写锁保护整棵树
// 方案3：改用不可变树实现（函数式数据结构，每次修改创建新树）
// 生产环境中，如果需要并发读写树结构，通常改用ConcurrentSkipListMap代替五、总结与延伸
非递归遍历的本质是手动管理"调用栈"，而不是一套需要背的技巧。 理解了"前序=入栈时访问，中序=出栈时访问，后序=判断右子树已访问再出栈"的统一框架，三种遍历的实现自然而然。
Morris遍历（O(1)空间）在面试里是加分项，但需要清楚它的代价：临时修改树结构。 实际工程中，内存不紧张的情况下，用显式栈的版本更安全、更易维护。Morris遍历更多是作为知识储备，证明你对树和指针有深入理解。
层序遍历（BFS）的关键技巧是用queue.size()截断每一层。 这个小技巧能解决一大类"按层处理"的树题目（最大深度、锯齿形层序、二叉树的右视图），掌握这个模式比单独记忆每道题更有价值。