如何用循环体结构重构基于递归的二叉树遍历？

循环遍历二叉树需用显式栈模拟递归：前序先访根再压右、左；中序先压左路径再弹根转右；后序可用标记法或逆先序+反转；层次遍历则用队列实现BFS。

用循环替代递归遍历二叉树，核心是用显式栈模拟系统调用栈的行为。递归靠函数调用隐式压栈，循环则需手动管理节点入栈、出栈和访问时机——关键不在“能不能”，而在“什么时候访问根节点”。

前序遍历：根→左→右，循环只需先处理再压栈

前序最直观：每次拿到一个节点，立刻访问它，再把右子树、左子树依次压栈（注意顺序：右先入，左后入，保证左先出）。

• 初始化栈，将根节点入栈
• 循环直到栈空：弹出节点 → 访问值 → 先压右子节点（若存在）→ 再压左子节点（若存在）
• 这样能严格复现“根-左-右”的访问顺序，代码简洁，不易出错

中序遍历：左→根→右，循环需“走到最左再回退”

中序不能一上来就访问根，必须先抵达最左侧叶子，再逐层向上访问根并转向右子树。

• 从根开始，一路向左，沿途节点全部入栈，直到左孩子为空
• 此时栈顶是最左节点，弹出并访问；然后切换到它的右子节点
• 对右子节点重复“一路向左入栈”过程
• 本质是把递归中“先递归左，再打印，再递归右”的逻辑，拆解为“压左路径→弹根→切右→再压左路径”

后序遍历：左→右→根，循环需区分“刚入栈”和“左右已处理完”

后序最难，因为根必须最后访问。单纯用栈无法判断某节点的左右子树是否已被处理，所以需要额外信息。

• 方法一（标记法）：栈中存节点+状态（如0=未处理左右，1=已处理左，2=已处理右）。每次弹出时根据状态决定是继续压左/右，还是直接访问
• 方法二（逆先序变形）：按“根→右→左”顺序遍历，结果反转。这样就能复用前序循环逻辑，仅调整入栈顺序（先压左，再压右），最后 reverse 输出数组
• 两种方式都可行，标记法更贴近原始逻辑，逆序法代码更简短

层次遍历：天然适合队列，不用栈

层次遍历按层展开，是广度优先，和递归调用栈的深度优先逻辑不同，因此不依赖栈，而用队列。

• 初始化队列，根节点入队
• 循环直到队列空：队首出队 → 访问 → 左子节点入队（若存在）→ 右子节点入队（若存在）
• 每轮只处理当前层所有节点，可配合 for 循环或记录层长度实现分层输出