显式栈模拟递归的关键是手动还原调用帧上下文，包括参数、局部变量和执行阶段；需用Frame结构封装全部状态，按逆序压栈并分stage控制流程，确保中间结果不丢失。
把递归改成用显式栈模拟，关键不是“去掉递归”，而是把系统自动管理的调用栈，换成你自己能看、能改、能中断的堆上数据结构。
核心是还原每层调用的完整上下文
递归函数每次调用，都会在系统栈里存一份帧（Frame）：参数、局部变量、执行到哪一步了、等谁返回。显式栈要做的，就是用一个对象把这些信息全装进去，再用数组或 Stack 类来管理它们。
比如一个典型 Frame 结构：
-
node或n：当前处理的主参数 -
leftRes、rightRes：中间计算结果，用于合并 -
stage：整数标记当前执行阶段，如0=刚进来、1=左子已处理完、2=右子已处理完
按逆序压栈，靠 stage 控制流程
递归天然有顺序（如“访问自己→递归左→递归右”），迭代中不能靠函数调用隐含顺序，得靠入栈顺序 + stage 判断来还原。
常见做法是：想让某部分后执行，就先把它压进去。
例如 DFS 前序遍历，想“先处理根、再左、再右”，就得把右子、左子、根（带 stage=0）按这个逆序压栈——这样 pop 出来时，才是根→左→右。
分阶段还原，避免逻辑错乱
特别是需要等待子结果的场景（如树的高度、表达式求值），必须靠 stage 区分状态：
- stage 0：初始化，压左子任务（stage=1）
- stage 1：拿到左子返回值，存进
leftRes，再压右子任务（stage=2） - stage 2：拿到右子返回值，填
rightRes，算max(leftRes, rightRes) + 1，作为本层结果返回给上层
这样每一层的变量生命周期、依赖关系、执行点都清晰可控。
树类问题可套用三段式模板
多数二叉树递归都能映射成三个 stage：
- 进入时：记录节点、清空中间量、压左子（stage=1）
- 左回后：存 leftRes、压右子（stage=2）
- 右回后：用两个子结果做合并，生成本层返回值
所有状态都在你定义的对象里，加日志、暂停、恢复、调试断点，都比纯递归方便得多。
注意别只存节点，漏掉中间状态
常见错误是只往栈里塞 node，结果发现 leftResult 不知存在哪、sum 每次都被重置。必须把“这一层还没做完的事”和“已经算出的部分结果”一起打包进 Frame，否则逻辑就断了。
