前序、中序、后序遍历本质是同一节点三次访问时机的选择：第一次抵达（前序）、左子树返回（中序）、右子树返回（后序）；需用栈+状态标记（如pair）显式模拟递归帧生命周期。
前序、中序、后序遍历的本质是访问时机不同
三种遍历不是“顺序不同”，而是对同一个节点的三次潜在访问机会中，选择哪一次真正输出。递归写法隐藏了这个事实：每次调用函数时，系统自动压栈；返回时自动弹栈。而手动模拟栈，就能看清每个节点被压入几次、何时被真正处理。
用显式栈还原递归的三段式访问
每个节点在遍历过程中实际会“出现”三次：
- 第一次抵达（刚入栈）→ 对应前序位置
- 从左子树返回（左已处理完）→ 对应中序位置
- 从右子树返回（左右都处理完）→ 对应后序位置
关键在于：不能只存节点指针，要标记当前处于哪一阶段。常用做法是用 pair
统一框架写出三种遍历的迭代版本
以下逻辑适用于所有三种遍历，仅改变 输出时机 和 入栈顺序：
- 初始 push(root, 0)
- while 非空：取顶，根据其 stage 决定：
- stage == 0：输出（前序点），push(当前, 1)，若左非空 push(左, 0)
- stage == 1：输出（中序点），push(当前, 2)，若右非空 push(右, 0)
- stage == 2：输出（后序点），直接 pop（不再 push）
你会发现：前序输出在 push 左之前；中序在 push 右之前；后序在彻底放弃该节点时。这就是栈里“调用帧生命周期”的真实映射。
看穿递归底层：一次递归调用 = 一个栈帧的完整生命周期
写一个最简递归前序：
void dfs(TreeNode* x) {if (!x) return;
cout val; // ← 前序动作
dfs(x->left);
dfs(x->right);
}
它等价于：
① 当前帧创建 → 压栈
② 执行本层逻辑（输出）
③ 调用 dfs(left) → 新帧压栈，等待 left 完全返回
④ left 返回 → 当前帧继续，调用 dfs(right)
⑤ right 返回 → 当前帧结束 → 弹栈
所谓“递归深度”，就是栈的最大高度；所谓“回溯”，就是不断弹栈回到上一层帧。手动栈不是替代递归，而是把隐式调用栈显性化、可观察、可调试。
