前序、中序、后序遍历本质是同一节点三次访问时机的选择：第一次抵达（前序）、左子树返回（中序）、右子树返回（后序）；需用栈+状态标记（如pair<TreeNode*, int>）显式模拟递归帧生命周期。

前序、中序、后序遍历的本质是访问时机不同

三种遍历不是“顺序不同”，而是对同一个节点的三次潜在访问机会中，选择哪一次真正输出。递归写法隐藏了这个事实：每次调用函数时，系统自动压栈；返回时自动弹栈。而手动模拟栈，就能看清每个节点被压入几次、何时被真正处理。

用显式栈还原递归的三段式访问

每个节点在遍历过程中实际会“出现”三次：

• 第一次抵达（刚入栈）→ 对应前序位置
• 从左子树返回（左已处理完）→ 对应中序位置
• 从右子树返回（左右都处理完）→ 对应后序位置

关键在于：不能只存节点指针，要标记当前处于哪一阶段。常用做法是用 pair<TreeNode*, int> 或封装一个状态结构体。例如：

stack<pair<TreeNode*, int>> stk; // second: 0=未访问, 1=左回, 2=右回

统一框架写出三种遍历的迭代版本

以下逻辑适用于所有三种遍历，仅改变 输出时机 和 入栈顺序：

• 初始 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 返回 → 当前帧结束 → 弹栈

所谓“递归深度”，就是栈的最大高度；所谓“回溯”，就是不断弹栈回到上一层帧。手动栈不是替代递归，而是把隐式调用栈显性化、可观察、可调试。