如何在JavaScript中按parentID将对象数组转为层级树形结构

你需要处理一组带有parentID字段的对象数组，将其按层级关系分组，生成包含children字段的树形结构，层级数量不限制。以下是具体的输入输出示例：

输入示例 #

[
  {
    "_id": "123",
    "name": "ABC",
    "parentID": ""
  },
  {
    "_id": "645",
    "name": "ABC 2",
    "parentID": "123"
  },
  {
    "_id": "65",
    "name": "ABC 3",
    "parentID": ""
  }
]

输出示例 #

[
  {
    "_id": "123",
    "name": "ABC",
    "parentID": "",
    "children": [
      {
        "_id": "645",
        "name": "ABC 2",
        "parentID": "123"
      }
    ]
  },
  {
    "_id": "65",
    "name": "ABC 3",
    "parentID": ""
  }
]

解决方案（JavaScript实现） #

可以通过以下高效步骤实现需求：

1. 构建ID与对象的映射表，实现O(1)时间复杂度的节点查找；
2. 遍历每个节点，根据parentID找到父节点，将当前节点挂载到父节点的children数组；
3. 最后收集所有parentID为空的根节点，组成最终树形结构。

完整代码如下：

function buildTree(items) {
  const idMap = {};
  const rootNodes = [];

  // 构建ID到节点的映射
  items.forEach(item => {
    idMap[item._id] = { ...item };
  });

  // 挂载子节点到对应父节点
  items.forEach(item => {
    if (item.parentID && idMap[item.parentID]) {
      if (!idMap[item.parentID].children) {
        idMap[item.parentID].children = [];
      }
      idMap[item.parentID].children.push(idMap[item._id]);
    } else if (!item.parentID) {
      rootNodes.push(idMap[item._id]);
    }
  });

  return rootNodes;
}

// 测试执行
const input = [
  { "_id": "123", "name": "ABC", "parentID": "" },
  { "_id": "645", "name": "ABC 2", "parentID": "123" },
  { "_id": "65", "name": "ABC 3", "parentID": "" }
];

console.log(JSON.stringify(buildTree(input), null, 2));

该方案时间复杂度为O(n)，支持任意层级的嵌套结构，只要节点的parentID能正确对应父节点的_id即可。

内容的提问来源于stack exchange，提问作者Đạt Huỳnh