用一个栈搞定二叉树前/中/后序遍历（非递归版）：把递归“翻译”成 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加进结果。
| 遍历 | 顺序 | 非递归共同骨架 | 访问时机 |
|---|---|---|---|
| 前序 | 根-左-右 | 左链压栈 + 转右 | 压栈/第一次遇到节点时访问 |
| 中序 | 左-根-右 | 左链压栈 + 转右 | 弹栈时访问（左完成后） |
| 后序 | 左-右-根 | 左链压栈 + 条件转右 | 左右都完成时访问（靠prev判断） |
5) 最容易踩的坑（建议贴在笔记顶部）
后序一定要有“右子树是否处理完”的判断
没有prev或等价机制，极容易死循环或顺序错。中序的关键动作是：pop 后访问，再转 right
少一步都会乱序。前序的关键是：访问要发生在走左之前
把add放到 pop 后，就变成中序/后序味道了。尽量用
ArrayDeque代替Stack（工程上更推荐）Stack是老类（继承自 Vector），同步开销大；Deque更现代更快。算法逻辑不变。
结尾：把递归“翻译”成迭代的诀窍
真正的诀窍不是背代码，而是把递归的三件事想明白：
- 递归“往下走” → 用
cur和while(cur != null)模拟 - 递归“回到父节点” → 用
stack保存路径 - 前/中/后序的区别 →访问发生在：下潜前 / 回溯时 / 左右都完成后
理解到这层，换题、换写法都不会慌。
)
