递归遍历对象数组计算嵌套包裹总额的实现难题

问题背景 #

现有一个项目对象数组，其中包含支持任意层级嵌套的包裹（Package），包裹分为展开/折叠两种状态：

• 展开状态：以BP（Begin Package）为起始标识，EP（End Package）为结束标识，中间包含子包裹或项目
• 折叠状态：仅存在BP标识，无对应EP，但计算总额时仍需包含其所有子包裹及项目的金额

当前仅能处理2层嵌套，核心障碍是折叠包裹无EP标识，无法准确跟踪嵌套层级，导致子包裹与父包裹关联错误，无法递归计算各层级总额（子包裹总额需计入父包裹总额）。

数据示例 #

const items = [
  { type: 'BP', id: 'pkg1', name: '一级包裹1', amount: 0, isCollapsed: false },
  { type: 'ITEM', id: 'item1', name: '项目1', amount: 100 },
  { type: 'BP', id: 'pkg2', name: '二级包裹2', amount: 0, isCollapsed: true, children: [
    { type: 'ITEM', id: 'item2-1', name: '折叠包裹子项目', amount: 200 }
  ] },
  { type: 'BP', id: 'pkg3', name: '二级包裹3', amount: 0, isCollapsed: false },
  { type: 'BP', id: 'pkg4', name: '三级包裹4', amount: 0, isCollapsed: false },
  { type: 'ITEM', id: 'item4', name: '项目4', amount: 150 },
  { type: 'EP', id: 'pkg4' },
  { type: 'EP', id: 'pkg3' },
  { type: 'EP', id: 'pkg1' },
  { type: 'BP', id: 'pkg5', name: '一级包裹5', amount: 0, isCollapsed: false },
  { type: 'ITEM', id: 'item5', name: '项目5', amount: 300 },
  { type: 'EP', id: 'pkg5' }
];

核心思路 #

用栈结构跟踪嵌套层级，结合递归计算节点总额：

1. 遍历数组时，用栈存储当前处于展开状态的包裹节点
2. 遇到BP：
   • 若为折叠状态：直接构建节点，基于内置children计算总额，关联到父包裹后无需入栈（无后续子项在数组中）
   • 若为展开状态：构建节点并压入栈，等待后续子项处理
3. 遇到ITEM：直接关联到栈顶的展开包裹，累计金额
4. 遇到EP：弹出栈顶包裹，递归计算其所有子项的总额并累加
5. 最终对所有根节点递归计算总额，确保层级嵌套的金额正确传递

实现代码 #

// 递归计算单个节点的总额（含子项）
function calculateNodeTotal(node) {
  if (node.type === 'ITEM') {
    return node.amount;
  }
  // 初始总额为包裹自身金额
  let total = node.amount || 0;
  // 累加所有子项的总额
  node.children.forEach(child => {
    total += calculateNodeTotal(child);
  });
  node.total = total;
  return total;
}

// 构建嵌套结构并计算所有包裹总额
function calculateAllPackageTotals(items) {
  const stack = [];
  const rootNodes = [];

  items.forEach(item => {
    switch (item.type) {
      case 'BP':
        const packageNode = {
          ...item,
          children: item.children || [] // 折叠包裹的子项预存在children中
        };
        // 关联到父包裹（栈顶为当前层级的父包裹）
        if (stack.length > 0) {
          stack[stack.length - 1].children.push(packageNode);
        } else {
          rootNodes.push(packageNode);
        }
        // 仅展开状态的包裹入栈，等待后续子项处理
        if (!item.isCollapsed) {
          stack.push(packageNode);
        } else {
          // 折叠包裹直接计算总额
          calculateNodeTotal(packageNode);
          // 若有父包裹，将总额累加到父包裹（后续统一计算也可）
          if (stack.length > 0) {
            stack[stack.length - 1].total = (stack[stack.length - 1].total || 0) + packageNode.total;
          }
        }
        break;
      case 'ITEM':
        // 项目仅属于当前栈顶的展开包裹
        if (stack.length > 0) {
          stack[stack.length - 1].children.push(item);
        } else {
          rootNodes.push(item);
        }
        break;
      case 'EP':
        // 弹出栈顶的展开包裹，计算其总额
        if (stack.length > 0) {
          const finishedPackage = stack.pop();
          calculateNodeTotal(finishedPackage);
          // 将总额累加到父包裹（若存在）
          if (stack.length > 0) {
            stack[stack.length - 1].total = (stack[stack.length - 1].total || 0) + finishedPackage.total;
          }
        }
        break;
    }
  });

  // 处理栈中剩余的展开包裹（理论上不会存在，除非数组不完整）
  stack.forEach(pkg => calculateNodeTotal(pkg));

  // 计算根节点的总额
  rootNodes.forEach(node => {
    if (node.type === 'BP') calculateNodeTotal(node);
  });

  return rootNodes;
}

// 调用示例
const result = calculateAllPackageTotals(items);
console.log(result);

代码说明 #

• 栈结构：仅跟踪展开状态的包裹，确保折叠包裹不会干扰后续子项的层级归属
• 递归计算：calculateNodeTotal函数递归遍历节点的所有子项，累计总额，支持无限层级嵌套
• 折叠包裹处理：假设折叠包裹的子项预存在children属性中，直接计算总额后关联到父包裹，无需等待EP标识

内容的提问来源于stack exchange，提问作者Dylan Layton