Node.js中树形结构父节点maxScore求和的高性能算法优化

Great question! Let's dive into how to optimize this parent-child sum calculation for better performance, especially as your dataset grows.

Why Your Current Approach Might Be Slow #

If your current implementation uses something like filtering the entire array for each parent node to find its children (then reducing to sum scores), it’s likely running in O(n²) time complexity. For example:

// Example of a common O(n²) approach
const parentScores = groups
  .filter(group => group.parent === null)
  .map(parent => {
    const children = groups.filter(child => child.parent === parent.id);
    return {
      parentId: parent.id,
      totalScore: parent.maxScore + children.reduce((sum, c) => sum + c.maxScore, 0)
    };
  });

This works fine for small datasets, but will slow down noticeably as the number of groups grows.

The High-Performance Alternative: Build a Parent-Child Map #

The most efficient approach is to first create a parent-to-children mapping table, which only requires two passes over the array (O(n) total time). After building this map, you can quickly look up children for any parent without re-traversing the entire dataset.

Step 1: Create the Parent-Child Mapping

First, iterate through the array once to store all children under their respective parent nodes (including handling parent: null for root nodes):

const groups = [{ id:1, parent:null, groupName:'Others', maxScore:3}, {id:2, parent:null, groupName: 'Group 1', maxScore:0}, {id:3, parent:2, groupName:'Others', maxScore:2}, {id:4, parent:2, groupName:'Sub Group 1', maxScore:1}];

// Use a Map to store parent nodes (supports null as a key)
const parentToChildren = new Map();

groups.forEach(group => {
  const parentKey = group.parent;
  if (!parentToChildren.has(parentKey)) {
    parentToChildren.set(parentKey, []);
  }
  parentToChildren.get(parentKey).push(group);
});

Step 2: Calculate Total Scores for Each Parent

Next, iterate through the array again to compute the total score for each parent node (including its own maxScore plus all children's scores):

const parentTotalScores = new Map();

groups.forEach(group => {
  // Get all children of the current node (empty array if none exist)
  const children = parentToChildren.get(group.id) || [];
  // Sum the current node's score plus all children's scores
  const total = group.maxScore + children.reduce((sum, child) => sum + child.maxScore, 0);
  parentTotalScores.set(group.id, total);
});

// Output result: Map(4) { 1 => 3, 2 => 3, 3 => 2, 4 => 1 }
console.log(parentTotalScores);

Additional Optimizations #

• Use Plain Objects for Faster Lookups: If your id and parent values are numbers or strings, a plain object might be slightly faster than a Map (thanks to native JS optimizations for object keys):

  const parentToChildren = {};
  groups.forEach(group => {
    // Convert null to a string key to avoid object key issues
    const parentKey = group.parent ?? 'root';
    if (!parentToChildren[parentKey]) {
      parentToChildren[parentKey] = [];
    }
    parentToChildren[parentKey].push(group);
  });
  

• Single-Pass Calculation (For Root Nodes Only): If you only need total scores for root nodes, you can compute sums while building the map to save an extra iteration (though this reduces readability slightly).

Why This Is Better #

By building a parent-child map, you cut the time complexity from O(n²) to O(n). For large datasets (think thousands of nodes), this makes a massive difference—you’ll avoid repeatedly scanning the entire array to find children, and instead pull them directly from the pre-built map.

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