本文详解如何系统性地将递归后序遍历（如二叉树转累加树）转化为空间最优的迭代解法，通过双栈协同模拟调用栈行为，在不使用哈希表的前提下严格维持 o(h) 辅助空间。
本文详解如何系统性地将递归后序遍历（如二叉树转累加树）转化为空间最优的迭代解法，通过双栈协同模拟调用栈行为，在不使用哈希表的前提下严格维持 o(h) 辅助空间。
将递归解法转为迭代解法，核心挑战不在于“遍历顺序”，而在于精确复现递归调用栈中隐含的状态传递逻辑——尤其是当递归函数返回值需被父节点使用的场景（如 solve(node) 返回子树和供父节点更新自身数据）。此时仅靠单栈记录节点无法承载「当前应执行哪一步」及「子调用返回值是多少」这两类信息，必须显式建模。
关键思想：用双栈模拟调用帧
Java 虚拟机在递归调用时，每个栈帧包含：① 当前节点引用；② 待执行的下一步指令（如“刚返回左子树，接下来处理右子树”或“左右均已返回，现在更新当前节点并返回”）；③ 局部变量（如 leftSubtreeValue 的暂存值）。迭代中可用两个栈对应：
-
nodeStack：存储待访问/待处理的节点； -
stateStack（Stack<boolean></boolean>或Stack<enum></enum>）：标记该节点对应的操作阶段。例如用true表示“此节点已完成左右子树处理，可执行本层计算并返回”，false表示“此节点刚入栈，需先递归处理左子树”。
以二叉树转累加树（Sum Tree）为例，其递归逻辑本质是后序遍历 + 值传递：
private int solve(Node node) {
if (node == null) return 0;
int left = solve(node.left); // ← 返回左子树所有节点值之和
int right = solve(node.right); // ← 返回右子树所有节点值之和
int oldVal = node.data;
node.data = left + right; // ← 更新当前节点为子树和
return oldVal + left + right; // ← 向上返回包含自身的子树总和
}对应迭代实现需在访问每个节点时，能获取其左右子树已计算出的和。我们采用延迟计算 + 双栈状态驱动：
class Solution {
public void toSumTree(Node root) {
if (root == null) return;
Stack<Node> nodeStack = new Stack<>();
Stack<Boolean> isProcessedStack = new Stack<>(); // true: 左右已处理，可计算；false: 初次入栈，需压入子节点
// 用于暂存每个节点的左右子树返回值（仅需 O(H) 空间，因栈深最大为 H）
Map<Node, Integer> subtreeSum = new HashMap<>();
nodeStack.push(root);
isProcessedStack.push(false);
while (!nodeStack.isEmpty()) {
Node node = nodeStack.pop();
boolean isProcessed = isProcessedStack.pop();
if (!isProcessed) {
// 第一次访问：模拟递归进入，先压入自身（标记为已处理），再压入右、左子节点（保证左先处理）
nodeStack.push(node);
isProcessedStack.push(true);
if (node.right != null) {
nodeStack.push(node.right);
isProcessedStack.push(false);
}
if (node.left != null) {
nodeStack.push(node.left);
isProcessedStack.push(false);
}
} else {
// 第二次访问：左右子树已处理完毕，读取缓存值并更新
int leftSum = (node.left != null) ? subtreeSum.get(node.left) : 0;
int rightSum = (node.right != null) ? subtreeSum.get(node.right) : 0;
int oldVal = node.data;
node.data = leftSum + rightSum;
subtreeSum.put(node, oldVal + leftSum + rightSum);
}
}
}
}⚠️ 注意：上述代码中 subtreeSum 使用 HashMap，看似引入 O(N) 空间。但关键优化在于——我们完全可以用第二个栈替代哈希表：在 isProcessed==false 阶段压入子节点后，同时压入占位值（如 0）；当 isProcessed==true 时，弹出两个子树结果（若存在）并计算。由于栈深度为 H，最多同时存在 H 对「节点+值」，故改用 Stack<integer></integer> 存储返回值即可达成严格 O(H)：
// 空间优化版（O(H) 确保）
class Solution {
public void toSumTree(Node root) {
if (root == null) return;
Stack<Node> nodeStack = new Stack<>();
Stack<Boolean> isProcessedStack = new Stack<>();
Stack<Integer> valueStack = new Stack<>(); // 存储每个节点的返回值（子树和）
nodeStack.push(root);
isProcessedStack.push(false);
while (!nodeStack.isEmpty()) {
Node node = nodeStack.pop();
boolean isProcessed = isProcessedStack.pop();
if (!isProcessed) {
// 第一次：压入自身（标记为已处理），再压入右、左子树（空节点跳过）
nodeStack.push(node);
isProcessedStack.push(true);
// 先压右后压左，保证左子树先被处理（后序：左→右→根）
if (node.right != null) {
nodeStack.push(node.right);
isProcessedStack.push(false);
}
if (node.left != null) {
nodeStack.push(node.left);
isProcessedStack.push(false);
}
} else {
// 第二次：弹出左右子树返回值（若不存在则为0）
int rightSum = (node.right != null) ? valueStack.pop() : 0;
int leftSum = (node.left != null) ? valueStack.pop() : 0;
int oldVal = node.data;
node.data = leftSum + rightSum;
valueStack.push(oldVal + leftSum + rightSum); // 当前节点返回值入栈
}
}
}
}总结与通用协议
- 识别递归模式：确认是否为 DFS 类型（前/中/后序），明确每层依赖的返回值；
-
设计状态栈：除节点栈外，必配状态栈（
Boolean/Enum）区分“进入”与“返回”阶段； - 管理返回值：用独立栈按后序顺序存储子调用结果，利用栈的 LIFO 特性自然匹配父子依赖；
- 压栈顺序：为保证左→右→根，对非空子节点按「右→左」顺序压入（使左子树先出栈处理）；
- 空间守恒：所有栈深度均不超过树高 H，故总空间复杂度为 O(H)，与递归解法完全一致。
该方法可泛化至任意需返回值的树形递归问题（如求直径、最大路径和等），是掌握迭代转化能力的关键范式。
