JavaScript中多级嵌套结构按层级汇总金额的递归实现-js教程-PHP中文网

JavaScript中多级嵌套结构按层级汇总金额的递归实现

本文详细介绍了如何使用递归方法高效地计算多级嵌套数据结构中每个层级的总金额。通过一个具体的JavaScript示例，我们将演示如何遍历树形结构，在每个层级聚合存款数据，并生成一个包含各层级总和的数组，从而解决在处理复杂层级数据时常见的汇总难题。

理解问题：多级结构中的层级汇总需求

在许多业务场景中，我们经常会遇到具有层级关系的数据，例如组织架构、推荐系统中的用户层级或产品分类。这类数据通常以嵌套对象或数组的形式存在，形成一个树状结构。一个常见的需求是，需要统计每个层级下特定属性（如存款、销售额等）的总和。

例如，我们有一个用户推荐系统，每个用户可能有自己的下级推荐用户（children），这些下级用户又可能有自己的下级，以此类推，最多可达5个层级。每个用户对象都包含一个deposit属性。我们的目标是计算并输出一个数组，其中每个元素代表对应层级所有用户的deposit总和。

原始数据结构示例（简化）：

[
    {
        "id": "ddf86d60-a607-4a4e-a7f9-d96013ee7070",
        "name": "Rick Rich",
        "deposit": 100,
        "children": [
            {
                "id": "25de2e98-eb2d-41f4-b225-3069f942b284",
                "name": "Rick Rich",
                "deposit": 100,
                "children": [
                    // 更深层级的children
                ]
            },
            { "id": "0ee1ea8f-790f-4767-b280-c5cddfe9c630", "name": "Rick Rich", "deposit": 100, "children": [] }
        ]
    },
    { "id": "d1022d3c-25af-461c-af91-cbc64147f92c", "name": "Rick Rich", "deposit": 100, "children": [] }
]

登录后复制

期望的输出格式是一个数组，例如 [300, 300, 300, 300]，其中每个数字对应一个层级的总存款。

错误的尝试与分析

初学者在处理这类问题时，可能会尝试使用简单的迭代或不恰当的递归，导致无法正确区分层级。例如，将所有节点的deposit值简单地收集到一个数组中，但这只会得到一个扁平化的列表，而非按层级汇总的结果。

立即学习“Java免费学习笔记（深入）”；

BibiGPT-哔哔终结者

B站视频总结器-一键总结音视频内容

查看详情

// 错误的尝试示例（仅为说明问题，与原问答中用户代码略有不同，但表达了相似的误区）
const getAllDepositsFlat = (children, result = []) => {
    children.forEach(node => {
        result.push(node.deposit);
        if (node.children && node.children.length > 0) {
            getAllDepositsFlat(node.children, result);
        }
    });
    return result;
};

// 假设传入上述简化数据，会得到 [100, 100, 100, 100, ...] 这样的扁平列表
// 这无法满足按层级汇总的需求

登录后复制

上述方法的问题在于，它遍历了所有节点并将deposit值无差别地添加到同一个结果数组中，没有区分不同层级的节点。要实现按层级汇总，我们需要在处理完一个层级的所有节点后，再汇总其deposit，然后才进入下一个层级的处理。

解决方案：基于递归的层级遍历与汇总

解决此问题的关键在于使用递归（或广度优先遍历的迭代方式），确保在每次递归调用中处理一个完整的层级，并收集其所有子节点以供下一次递归。

核心思路

当前层级汇总： 在每次递归调用开始时，遍历当前层级的所有节点，计算它们的deposit总和。
收集下一层级： 在遍历当前层级节点的同时，将所有节点的children收集起来，形成一个包含所有下一层级节点的数组。
存储结果： 将当前层级的deposit总和添加到最终结果数组中。
递归调用： 如果收集到的下一层级节点数组不为空，则以这个数组作为参数，再次调用递归函数，处理下一个层级。

示例代码

// 假设这是我们的原始数据，为了演示方便，进行了简化
let hierarchicalData = [
    {
        "deposit": 100,
        "children": [
            {
                "deposit": 100,
                "children": [
                    {
                        "deposit": 100,
                        "children": [
                            { "deposit": 100 }, // Level 4
                            { "deposit": 100 }, // Level 4
                            { "deposit": 100 }  // Level 4
                        ]
                    },
                    { "deposit": 100, "children": [] }, // Level 3
                    { "deposit": 100, "children": [] }  // Level 3
                ]
            },
            { "deposit": 100, "children": [] }, // Level 2
            { "deposit": 100, "children": [] }  // Level 2
        ]
    },
    { "deposit": 100, "children": [] }, // Level 1
    { "deposit": 0, "children": [] }    // Level 1
];

let levelWiseDeposits = []; // 用于存储最终结果的数组

/**
 * 递归函数：计算并汇总多级嵌套结构中每个层级的存款总额
 * @param {Array<Object>} children - 当前层级的节点数组
 * @param {Array<number>} result - 存储各层级总额的数组（通过引用传递）
 */
function iterateOfChildrenDeposit(children, result) {
    let nextLevelChildren = []; // 用于存储下一层级的所有子节点
    let currentLevelTotalDeposit = 0; // 当前层级的存款总和

    // 遍历当前层级的所有节点
    children.forEach((node) => {
        currentLevelTotalDeposit += node.deposit; // 累加当前节点的存款
        // 如果当前节点有子节点，则将其添加到 nextLevelChildren 数组中
        if (node.children && node.children.length > 0) {
            nextLevelChildren = nextLevelChildren.concat(node.children);
        }
    });

    // 将当前层级的总存款添加到结果数组中
    result.push(currentLevelTotalDeposit);

    // 如果下一层级有节点，则递归调用自身处理下一层级
    if (nextLevelChildren.length > 0) {
        iterateOfChildrenDeposit(nextLevelChildren, result);
    }
    // 如果没有下一层级节点，递归结束
}

// 调用函数开始计算
iterateOfChildrenDeposit(hierarchicalData, levelWiseDeposits);

// 输出结果
console.log(levelWiseDeposits); // 预期输出: [300, 300, 300, 300]

登录后复制

代码解析

levelWiseDeposits = []: 初始化一个空数组，用于收集每个层级的总存款。这个数组是通过引用传递给递归函数的，因此所有层级的总和都会累积到其中。
iterateOfChildrenDeposit(children, result): 这是核心递归函数。
- children: 代表当前正在处理的层级的所有节点。
- result: 存储最终结果的数组。
nextLevelChildren = []: 在每次递归调用开始时，初始化一个空数组，用于收集当前层级所有节点的子节点。这些子节点将构成下一层级。
currentLevelTotalDeposit = 0: 初始化当前层级的存款总和。
children.forEach((node) => { ... }): 遍历当前层级的所有节点。
- currentLevelTotalDeposit += node.deposit: 将当前节点的存款累加到 currentLevelTotalDeposit 中。
- if (node.children && node.children.length > 0): 检查当前节点是否有子节点。如果有，则使用 concat 方法将这些子节点添加到 nextLevelChildren 数组中。concat 是为了确保将所有子节点（可能来自不同父节点）合并到一个数组中。
result.push(currentLevelTotalDeposit): 当前层级的所有节点处理完毕后，将 currentLevelTotalDeposit（即当前层级的总存款）添加到 result 数组中。
if (nextLevelChildren.length > 0) { ... }: 这是一个重要的递归终止条件。如果 nextLevelChildren 不为空，说明还有下一层级需要处理，于是以 nextLevelChildren 作为新的 children 参数，递归调用 iterateOfChildrenDeposit 函数。如果 nextLevelChildren 为空，则表示已经到达最底层，递归结束。

注意事项与总结

数据结构一致性: 确保输入数据中的每个节点都包含 deposit 属性，并且子节点通过 children 数组表示。即使没有子节点，children 属性也最好是一个空数组或不存在，这样可以避免在 if (node.children) 判断时出错。
最大层级: 这种递归方法能够自然地处理任意深度的层级，不受限于预设的5层限制。当某个层级没有子节点时，递归会自动终止。
性能考量: 对于非常深（例如几千层）或非常宽（每个层级有大量节点）的树形结构，递归可能会导致栈溢出。在这种极端情况下，可以考虑使用迭代式的广度优先遍历（BFS）结合队列来实现相同的功能，以避免递归深度限制。然而，对于5层左右的深度，递归通常是高效且易于理解的。
结果数组的传递: 示例中 result 数组是作为参数传递的，并且在函数内部被修改。这是一种常见的做法。如果需要函数具有更强的纯洁性（不修改外部状态），可以考虑让函数返回新的数组，但这会使递归逻辑稍微复杂一些。
错误处理: 实际应用中，可能需要增加对 node.deposit 是否为有效数字的检查，以提高代码的健壮性。