JavaScript中如何将记录列表与父记录指针树按规则合并

核心思路 #

整个实现分两步走：先通过迭代DFS拿到树节点的前序遍历序列，再遍历序列计算每个节点对应的记录区间，直接从预排序的listOfRecords中切片挂载即可。

具体实现代码（JavaScript示例） #

// 第一步：迭代DFS获取前序遍历的节点序列
function getDfsOrder(root) {
  const stack = [root];
  const order = [];
  // 栈为后进先出，子节点倒序入栈保证遍历顺序和原children顺序一致
  while (stack.length) {
    const node = stack.pop();
    order.push(node);
    if (node.children?.length) {
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i]);
      }
    }
  }
  return order;
}

// 第二步：给每个节点挂载对应records
function fillTreeWithRecords(treeRoot, listOfRecords) {
  const nodeOrder = getDfsOrder(treeRoot);
  // 预存record的ID到索引的映射，ID非连续场景也能快速查找
  const idToIndex = new Map(listOfRecords.map((record, idx) => [record.id, idx]));
  const maxRecordId = listOfRecords.at(-1).id;

  for (let i = 0; i < nodeOrder.length; i++) {
    const currentNode = nodeOrder[i];
    const startId = currentNode.id;
    // 下一个节点ID减1为当前节点结束ID，最后一个节点用最大record ID
    const endId = i < nodeOrder.length - 1 ? nodeOrder[i + 1].id - 1 : maxRecordId;
    
    // 跳过无效区间
    if (startId > endId) {
      currentNode.records = [];
      continue;
    }

    // 从listOfRecords中取对应区间的记录
    const startIdx = idToIndex.get(startId);
    const endIdx = idToIndex.get(endId);
    currentNode.records = listOfRecords.slice(startIdx, endIdx + 1);
  }

  return treeRoot;
}

// 调用示例
const filledTree = fillTreeWithRecords(treeOfParents, listOfRecords);

注意事项 #

• 如果listOfRecords的ID是从0开始连续递增的，可以省略idToIndex映射，直接用startId和endId作为下标取值，性能更高
• 若树节点的ID本身不保证有序，只需调整DFS遍历后的序列排序规则即可，无需修改挂载逻辑
• 迭代DFS的写法避免了深层树递归栈溢出的问题，适合任意层级的树结构

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