【码道初阶】【Leetcode94144145】二叉树的前中后序遍历（非递归版）：显式调用栈的优雅实现

用一个栈搞定二叉树前/中/后序遍历（非递归版）：把递归“翻译”成 while 循环

很多人写递归遍历很顺手，但一到非递归就开始迷糊：栈怎么压？什么时候弹？为什么后序还要prev？

其实核心只有一句话：

非递归遍历 = 用显式栈模拟递归调用栈，再用“访问时机”决定前/中/后序。

三种遍历的区别不在“走法”，而在“什么时候把节点加入结果”。

• 前序：第一次见到节点就访问（根最早）
• 中序：左边走到底后，弹栈时访问（根居中）
• 后序：左右都处理完，最后才访问（根最晚）（所以需要额外信息判断“右子树是否已经处理过”）

下面按你给的三段代码逐段讲。

0. 先统一一个“心智模型”：栈里装的是什么？

递归遍历时，每次函数调用会把“当前节点”和“接下来要做的事”压到调用栈里。
非递归就是把“当前节点”手动压到stack，并用cur指针控制下一步去哪。

常见骨架长这样：

while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}// 到这里说明：左链走到底了TreeNodetop=stack.pop()or stack.peek();// ...访问 or 转向右子树...}

差别在：

• 前序：压栈时就访问
• 中序：弹栈时访问
• 后序：满足“左右都完成”才弹栈并访问

1) 中序遍历（左-根-右）非递归：最经典模板

中序代码：

classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){//左根右Stack<TreeNode>stack=newStack<>();List<Integer>list=newArrayList<>();TreeNodecur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}TreeNodetop=stack.pop();list.add(top.val);cur=top.right;}returnlist;}}

过程讲解（像在走图）

Step A：一路向左“钻到底”，沿途压栈

while(cur!=null){stack.push(cur);cur=cur.left;}

这一步把从当前节点出发的“左链”全部压栈。
压栈顺序大概就是：根、根的左、左的左……

Step B：左边到头了，开始“回溯”

TreeNodetop=stack.pop();list.add(top.val);cur=top.right;

• pop()代表：递归里“左子树做完了，回到当前节点”
• 此时访问top，就实现了“左-根”
• 然后cur = top.right转向右子树，继续同样流程

为什么是中序？

因为访问发生在左子树处理完之后、右子树开始之前，刚好是“左根右”的根位置。

✅ 这份代码可以当作中序非递归的“标准答案模板”。

2) 后序遍历（左-右-根）非递归：关键在prev

后序代码：

classSolution{publicList<Integer>postorderTraversal(TreeNoderoot){List<Integer>list=newArrayList<>();if(root==null)returnlist;Stack<TreeNode>stack=newStack<>();TreeNodecur=root;TreeNodeprev=null;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}TreeNodetop=stack.peek();if(top.right==null||top.right==prev){list.add(top.val);stack.pop();prev=top;}else{cur=top.right;}}returnlist;}}

为什么后序比中序难？

后序要“根最后访问”。
但当左链走到底时，栈顶节点的左子树确实做完了——可右子树可能还没做。
所以不能像中序那样直接pop()访问。

这就是prev的意义：

prev记录“刚刚完成访问（出栈）的节点”，用它判断右子树是不是已经处理过。

过程拆解（核心分支只看这一段）

TreeNodetop=stack.peek();if(top.right==null||top.right==prev){// 右子树为空 或 右子树刚处理完visit(top);pop(top);prev=top;}else{// 右子树存在且没处理cur=top.right;}

情况 1：top.right == null

右子树为空，那就说明：

• 左子树已经完成（因为能来到 peek）
• 右子树不存在
• 所以当前节点可以访问（根最后）

情况 2：top.right == prev

这句是精髓：
“栈顶节点的右孩子刚刚被访问完”，说明右子树已经处理完毕。
于是当前节点也满足“左右都完成”，可以访问并出栈。

情况 3：右子树存在且未处理

这时候不能访问根，必须先去右子树：

cur=top.right;

然后循环会再次走 “一路向左压栈”，把右子树的左链压进去。

为什么这一定是后序？

因为每个节点只有在左子树完成且右子树完成之后才会被访问，根必然最后。

⭐ 易错点重点标识

• 如果没有prev，很容易在“从右子树回来”时无法判断是否该访问根，导致反复进入右子树或死循环。
• peek()必须配合条件判断；这里不能直接pop()，否则会提前访问根，顺序变坏。

3) 前序遍历（根-左-右）非递归：访问时机前移

前序代码：

classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>list=newArrayList<>();if(root==null)returnlist;Stack<TreeNode>stack=newStack<>();TreeNodecur=root;stack.push(cur);while(!stack.isEmpty()){while(cur!=null){stack.push(cur);list.add(cur.val);cur=cur.left;}TreeNodetop=stack.pop();cur=top.right;}returnlist;}}

先讲它的核心思想

前序要求“根最先访问”。
所以访问时机要比中序更早：第一次遇到节点就访问。

你这份代码确实做到了：在压栈时就list.add(cur.val)。

while(cur!=null){stack.push(cur);list.add(cur.val);cur=cur.left;}

然后左链走完，弹一个节点出来，转向它的右子树：

TreeNodetop=stack.pop();cur=top.right;

但这里有个小提醒（实现细节）

这段代码里有一行：

stack.push(cur);// 进入 while 前又 push 了一次 root

而在循环里又stack.push(cur)，因此根节点会被压栈两次（不过访问只发生一次，所以结果通常不受影响，但栈操作会冗余，逻辑也不够干净）。

更常见、更“干净”的前序非递归写法通常是下面两种之一：

写法 A：一路向左，访问并压栈（不需要额外先 push）

publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();Deque<TreeNode>stack=newArrayDeque<>();TreeNodecur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){res.add(cur.val);// 前序：先访问stack.push(cur);cur=cur.left;}TreeNodetop=stack.pop();cur=top.right;}returnres;}

写法 B：标准“栈模拟”模板（弹出就访问，先压右再压左）

publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();if(root==null)returnres;Deque<TreeNode>stack=newArrayDeque<>();stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();res.add(node.val);if(node.right!=null)stack.push(node.right);if(node.left!=null)stack.push(node.left);}returnres;}

两种都对。写法 A 和你中序的骨架更一致，适合“统一模板记忆”；写法 B 很直观，适合初学者。

4) 三种遍历的对照总结：差别只在“访问时机”

把三段代码放在一起看，其实只改了一个点：什么时候把top.val加进结果。

5) 最容易踩的坑（建议贴在笔记顶部）

1. 后序一定要有“右子树是否处理完”的判断
   没有prev或等价机制，极容易死循环或顺序错。

2. 中序的关键动作是：pop 后访问，再转 right
   少一步都会乱序。

3. 前序的关键是：访问要发生在走左之前
   把add放到 pop 后，就变成中序/后序味道了。

4. 尽量用ArrayDeque代替Stack（工程上更推荐）
   Stack是老类（继承自 Vector），同步开销大；Deque更现代更快。算法逻辑不变。

结尾：把递归“翻译”成迭代的诀窍

真正的诀窍不是背代码，而是把递归的三件事想明白：

• 递归“往下走” → 用cur和while(cur != null)模拟
• 递归“回到父节点” → 用stack保存路径
• 前/中/后序的区别 →访问发生在：下潜前 / 回溯时 / 左右都完成后

理解到这层，换题、换写法都不会慌。