如何学习将递归解决方案转换为迭代解决方案，同时保留空间复杂度？

Question

我正在尝试解决一个简单的二叉树问题，将现有的二叉树转换为求和树。 递归解决方案是：

class Solution{
    public void toSumTree(Node root){
         solve(root);
    }
    private int solve(Node node){
        if(node == null){
            return 0;
        }
        
        int leftSubtreeValue = solve(node.left);
        int rightSubtreeValue = solve(node.right);
        int currentNodeValue = node.data;
        
        node.data = leftSubtreeValue + rightSubtreeValue;
        
        return currentNodeValue + leftSubtreeValue + rightSubtreeValue;
    }
}

这给我们时间和空间复杂度分别为 O(N) 和 O(H)。

现在，由于上述递归方法类似于后序遍历，我认为我们可以使用某种版本的迭代后序遍历，如下所示：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) { 
        List<Integer> postOrderTrvNodes = new LinkedList<>();
        if(root == null){
             return postOrderTrvNodes;
         }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode lastVisited = null;
        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                TreeNode peekNode = stack.peek();
                if (peekNode.right != null && peekNode.right != lastVisited) {
                    current = peekNode.right;
                } else {
                    TreeNode poppedNode = stack.pop();
                    postOrderTrvNodes.add(poppedNode.val);
                    lastVisited = poppedNode;
                }
            }
        }
        return postOrderTrvNodes;
    }
}

我无法想出的是如何在每个节点存储所需的子树之和，以使空间复杂度保持为 O(H)。如果我们使用 HashMap 来存储 HashMap 中当前节点的子树之和，那么空间复杂度将变为 O(N)。

我想要的是一些可以普遍遵循的协议来模仿 Java 使用内部堆栈所做的事情。

Answer 1

您可以使用迭代方法来模拟递归解决方案的行为，而无需使用 HashMap 等附加数据结构。 这是修改后的迭代方法：

class Solution {
    public void toSumTree(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode lastVisited = null;

        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                TreeNode peekNode = stack.peek();
                if (peekNode.right != null && peekNode.right != lastVisited) {
                    current = peekNode.right;
                } else {
                    TreeNode poppedNode = stack.pop();

                    // Save the original value of the current node
                    int originalValue = poppedNode.val;

                    // Update the current node value with the sum of left and right subtrees
                    poppedNode.val = getSubtreeSum(poppedNode.left) + getSubtreeSum(poppedNode.right);

                    // Update the lastVisited to the current node
                    lastVisited = poppedNode;

                    // Update the parent node with the new value
                    if (!stack.isEmpty()) {
                        TreeNode parentNode = stack.peek();
                        if (parentNode.left == poppedNode) {
                            parentNode.left.val = originalValue;
                        } else {
                            parentNode.right.val = originalValue;
                        }
                    }
                }
            }
        }
    }

    private int getSubtreeSum(TreeNode node) {
        return (node != null) ? node.val : 0;
    }
}

在此代码中：

我们使用堆栈以类似后序的方式遍历树， 类似于您的初始代码。
我们使用

2. lastVisited 变量来跟踪我们最后访问的节点 处理。这让我们能够区分左和右 使用新值更新父节点时的子树。

我们维护当前节点的原始值（

3. originalValue） 计算左子树和右子树的总和。

我们用当前节点的 left 和 left 的和来更新当前节点的值 右子树。
如果当前节点不是根节点，我们也会更新父节点 相应的节点值。
这种方法确保空间复杂度保持为 O(H)，因为它只使用调用堆栈进行递归，并且不依赖于 HashMap 等额外的数据结构。

祝你好运:)