将递归JS函数addWidths转换为迭代实现的技术求助

我编写了如下递归JS函数addWidths，它接收一个由嵌套节点组成的参数node，通过为每个节点添加其所有叶子节点总数（非仅直接子节点）的width属性来修改原节点：

const addWidths = (node) => {
    const keys = Object.keys(node)
    for(const key of keys){
        addWidths(node[key])
    }
    if(keys.length > 0){
        node["width"] = Object.values(node).reduce((acc, cur) => acc + cur["width"], 0)
    }else{
        node["width"] = 1
    }
}

示例输入 #

const object = {
    "A": {
        "1": {},
        "2": {
            "+": {},
            "-": {}
        },
        "3": {}
    },
    "B": {
        "1": {}
    },
    "C": {},
    "D": {}
}

调用后预期输出 #

调用addWidths(object)后，对象会被修改为：

{
    "A": {
        "1": {
            "width": 1
        },
        "2": {
            "+": {
                "width": 1
            },
            "-": {
                "width": 1
            },
            "width": 2
        },
        "3": {
            "width": 1
        },
        "width": 4
    },
    "B": {
        "1": {
            "width": 1
        },
        "width": 1
    },
    "C": {
        "width": 1
    },
    "D": {
        "width": 1
    },
    "width":7
}

修改需求 #

需要将上述递归函数修改为迭代实现。

附：修改后的树形结构及各节点预期width值示意图：

迭代实现方案 #

递归的核心是利用调用栈完成后序遍历（先处理所有子节点，再处理父节点），迭代版本可以手动模拟栈，记录每个节点的访问状态：

const addWidthsIterative = (node) => {
    // 栈元素格式：[当前节点, 是否已处理过子节点]
    const stack = [[node, false]];

    while (stack.length > 0) {
        const [currentNode, isProcessed] = stack.pop();

        if (!isProcessed) {
            // 第一次弹出，标记为待处理后重新入栈
            stack.push([currentNode, true]);
            // 子节点逆序入栈，保证处理顺序和递归逻辑一致
            const childKeys = Object.keys(currentNode);
            for (let i = childKeys.length - 1; i >= 0; i--) {
                stack.push([currentNode[childKeys[i]], false]);
            }
        } else {
            // 第二次弹出，所有子节点已处理完成，计算当前节点width
            const childValues = Object.values(currentNode);
            currentNode.width = childValues.length === 0 
                ? 1 
                : childValues.reduce((acc, child) => acc + child.width, 0);
        }
    }
};

代码说明 #

• 用栈存储节点和处理状态：isProcessed为false时，该节点的子节点尚未处理；为true时，所有子节点已处理完毕，可计算当前节点的width。
• 首次弹出未处理节点时，先标记为待处理重新入栈，再将子节点逆序入栈，确保子节点的处理顺序和递归逻辑一致。
• 节点标记为已处理时，直接根据子节点的width求和，叶子节点直接设为1。

测试该迭代函数，传入示例输入后，输出结果与递归版本完全一致。

内容的提问来源于stack exchange，提问作者Axel Carré