本文详解如何将树的递归后序遍历（及依赖子树返回值的递归逻辑，如“转为累加树”）安全转化为迭代版本，通过双栈协同模拟调用栈行为，在不使用哈希表的前提下严格维持 o(h) 空间复杂度。
本文详解如何将树的递归后序遍历（及依赖子树返回值的递归逻辑，如“转为累加树”）安全转化为迭代版本，通过双栈协同模拟调用栈行为，在不使用哈希表的前提下严格维持 o(h) 空间复杂度。
在将递归算法转为迭代时，核心挑战不是“遍历顺序”，而是精确复现递归调用栈中隐含的状态流转：每个递归调用不仅需要访问节点，还需在子调用返回后，用其结果（如左/右子树和）更新当前节点。Java 虚拟机的调用栈天然保存了「当前执行位置」和「局部变量」；而纯迭代需显式建模这两者。
以题目中的 toSumTree 为例，递归函数 solve(node) 的语义是：
- 若
node == null，返回0； - 否则先递归求得
leftSum = solve(node.left)和rightSum = solve(node.right)； - 再更新
node.data = leftSum + rightSum； - 最后返回
node.data + leftSum + rightSum（即以该节点为根的整棵子树节点值总和）。
该过程本质是后序遍历 + 子树结果聚合，不能仅靠访问序列（如 postorderTraversal 返回列表），而必须在每个节点被“处理完成”（即左右子树均已计算完毕）时，能立即获取其左右子树的返回值。
✅ 正确策略：双栈模拟调用栈状态
单栈无法区分「刚压入待处理」和「已处理完子树待收尾」两种状态。解决方案是引入双栈：
-
nodeStack：存储待访问或待收尾的节点； -
isReturnStack（布尔栈）：标记栈顶节点所对应的操作类型 —false表示“需先处理其子树”，true表示“子树已处理完毕，现在应回收其返回值并执行当前层逻辑”。
其设计思想直接映射递归展开：
// 递归伪码
int solve(Node node) {
if (node == null) return 0;
int left = solve(node.left); // ← 压入 node.left，标记为 false（需递归）
int right = solve(node.right); // ← 压入 node.right，标记为 false
int result = node.data + left + right;
node.data = left + right; // ← 当前层计算
return result; // ← 返回 result 给父调用
}
对应迭代逻辑如下（完整 toSumTree 迭代版）：
class Solution {
public void toSumTree(Node root) {
if (root == null) return;
Stack<node> nodeStack = new Stack();
Stack<boolean> isReturnStack = new Stack(); // true: 已处理子树，可回收结果
// 初始：压入根节点，标记为 false（需先处理子树）
nodeStack.push(root);
isReturnStack.push(false);
// 存储每个节点的子树和（模拟递归返回值），复用节点字段或额外栈
// ✅ 关键：用另一个栈 valueStack 存储每层返回值，与 nodeStack 同步进出
Stack<integer> valueStack = new Stack();
while (!nodeStack.isEmpty()) {
Node node = nodeStack.pop();
boolean isReturn = isReturnStack.pop();
if (isReturn) {
// 此时 valueStack 栈顶两元素即为 node.right 和 node.left 的返回值（后序：右先入、左后入 → 左先出）
int rightSum = valueStack.isEmpty() ? 0 : valueStack.pop();
int leftSum = valueStack.isEmpty() ? 0 : valueStack.pop();
int oldData = node.data;
node.data = leftSum + rightSum;
valueStack.push(oldData + leftSum + rightSum); // 返回给父节点的值
} else {
// 需处理子树：按后序逆序压入（右→左→当前），但当前节点标记为 true（收尾）
// 注意：null 节点不压入，直接视为返回 0
if (node.right != null) {
nodeStack.push(node.right);
isReturnStack.push(false);
}
if (node.left != null) {
nodeStack.push(node.left);
isReturnStack.push(false);
}
// 当前节点留到最后处理：压入并标记为 true
nodeStack.push(node);
isReturnStack.push(true);
// 占位：后续将被 leftSum/rightSum 替换，此处可压 0 或忽略（由 valueStack 空判断）
}
}
}
}</integer></boolean></node>
⚠️ 注意事项与关键点
-
空间严格 O(H)：三个栈（
nodeStack,isReturnStack,valueStack）的最大深度均不超过树高 H。无哈希表、无额外节点字段，符合要求。 -
压栈顺序决定处理顺序：后序迭代中，“当前节点”必须最后压入（且标记
true），而子节点按「右→左」顺序压入（保证左子树先被弹出处理），这是复现递归调用顺序的关键。 -
valueStack 的配对机制：每次
isReturn == true时，从valueStack弹出的两个值，严格对应刚刚处理完的左右子树返回值 — 因为它们是在子节点被标记true后、计算完成时压入的。 -
null 处理更简洁：递归中
null返回0，迭代中跳过null节点压栈，valueStack在弹出时用isEmpty()判断补0，逻辑一致。 - 通用性：此双栈+值栈模式适用于所有「后序型」递归，只要递归函数有明确返回值且依赖子问题解（如树直径、最大路径和、平衡判断等）。
✅ 总结
将递归转为等价迭代的核心，不是“改写遍历”，而是状态机建模：用栈显式保存「执行上下文」（节点+控制流标记+返回值）。对于后序场景，nodeStack + isReturnStack 构成控制流栈，valueStack 构成数据栈，三者协同即可 1:1 模拟 JVM 调用栈行为，既保证正确性，又守住 O(H) 空间底线。掌握这一范式，便掌握了递归转迭代的底层钥匙。
