如何在JavaScript中递归将对象数组的子对象分组到父对象下

问题描述 #

我有一个扁平的主题数组，每个主题包含id、name和parent_id字段，其中parent_id关联父主题的id（根主题的parent_id为null）。需要将所有子主题嵌套到对应父主题的children数组中，形成层级结构。

示例输入 #

主题表：

对应的JSON数组：

[
  { id: 1, name: "Topic 1", parent_id: null },
  { id: 2, name: "Topic 2", parent_id: 1 },
  { id: 3, name: "Topic 3", parent_id: 2 },
  { id: 4, name: "Topic 4", parent_id: 2 },
  { id: 5, name: "Topic 5", parent_id: 4 }
]

期望输出 #

[
  {
    id: 1,
    name: "Topic 1",
    children: [
      {
        id: 2,
        name: "Topic 2",
        children: [
          { id: 3, name: "Topic 3", children: [] },
          {
            id: 4,
            name: "Topic 4",
            children: [
              { id: 5, name: "Topic 5", children: [] }
            ]
          }
        ]
      }
    ]
  }
]

解决方案 #

可以通过哈希表映射+迭代的方式高效构建层级结构，步骤如下：

实现代码 #

function buildHierarchy(topics) {
  // 1. 创建ID到主题的映射，同时给每个主题初始化空children数组
  const topicMap = {};
  topics.forEach(topic => {
    topicMap[topic.id] = { ...topic, children: [] };
  });

  // 2. 遍历主题，将子主题挂载到对应父主题下
  const hierarchy = [];
  topics.forEach(topic => {
    const current = topicMap[topic.id];
    if (topic.parent_id === null) {
      // 根主题直接加入结果数组
      hierarchy.push(current);
    } else {
      // 找到父主题，将当前主题加入其children
      const parent = topicMap[topic.parent_id];
      parent?.children.push(current);
    }
  });

  return hierarchy;
}

// 使用示例
const inputTopics = [
  { id: 1, name: "Topic 1", parent_id: null },
  { id: 2, name: "Topic 2", parent_id: 1 },
  { id: 3, name: "Topic 3", parent_id: 2 },
  { id: 4, name: "Topic 4", parent_id: 2 },
  { id: 5, name: "Topic 5", parent_id: 4 }
];

const nestedResult = buildHierarchy(inputTopics);
console.log(JSON.stringify(nestedResult, null, 2));

方法说明 #

1. 建立映射表：通过一次遍历，把每个主题以id为键存入对象，同时为每个主题添加空的children数组，这样后续查找父主题的时间复杂度是O(1)。
2. 构建层级：再次遍历所有主题，根主题直接加入结果数组；非根主题则找到对应的父主题，将自身添加到父主题的children数组中。

这种方法的时间复杂度为O(n)，n是主题总数，效率较高，适合处理大规模数据集。

内容的提问来源于stack exchange，提问作者Muhammad Kazim Sadiq