如何将单层对象数组转换为嵌套对象数组

给定如下单层对象数组：

const data = [ 
  {"id": 1, "catTitle": "Item1", "parentId": null },
  {"id": 2, "catTitle": "Item2", "parentId": null },
  {"id": 3, "catTitle": "Item3", "parentId": null },
  {"id": 4, "catTitle": "Item4", "parentId": 1 },
  {"id": 5, "catTitle": "Item5", "parentId": 1 },
  {"id": 6, "catTitle": "Item6", "parentId": 2 },
  {"id": 7, "catTitle": "Item7", "parentId": 2 },
  {"id": 8, "catTitle": "Item8", "parentId": 3 },
  {"id": 9, "catTitle": "Item9", "parentId": 5 },
  {"id": 10, "catTitle": "Item10", "parentId": 5 },
  {"id": 11, "catTitle": "Item11", "parentId": 7 },
  {"id": 12, "catTitle": "Item12", "parentId": 10 },
];

需要将其转换为带有childs属性的树形结构，每个节点的parentId对应父节点的id，预期结果示例如下：

const result = [
  {
    "id": 1,
    "catTitle": "Item1",
    "parentId": null,
    "childs": [{
        "id": 4,
        "catTitle": "Item4",
        "parentId": 1,
        "childs": []
      },
      {
        "id": 5,
        "catTitle": "Item5",
        "parentId": 1,
        "childs": [{
            "id": 9,
            "catTitle": "Item9",
            "parentId": 5,
            "childs": []
          },
          {
            "id": 10,
            "catTitle": "Item10",
            "parentId": 5,
            "childs": [{
              "id": 12,
              "catTitle": "Item12",
              "parentId": 10,
              "childs": []
            }]
          },
        ]
      },
    ]
  },
  // 其他节点结构类似...
];

解决方案 #

方法一：递归实现 #

先筛选出所有根节点（parentId为null的节点），然后对每个根节点递归查找其子节点，构建树形结构：

function buildTree(data) {
  // 递归查找指定父ID的子节点
  const getChildren = (parentId) => {
    return data
      .filter(item => item.parentId === parentId)
      .map(item => ({
        ...item,
        childs: getChildren(item.id)
      }));
  };

  // 返回根节点及其子树
  return getChildren(null);
}

// 使用示例
const treeResult = buildTree(data);
console.log(treeResult);

方法二：哈希表辅助的迭代实现 #

通过哈希表存储每个节点的引用，避免重复遍历数组，提升处理效率：

function buildTreeWithMap(data) {
  const nodeMap = new Map();
  const tree = [];

  // 第一步：将所有节点存入哈希表，同时初始化childs属性
  data.forEach(item => {
    nodeMap.set(item.id, { ...item, childs: [] });
  });

  // 第二步：遍历节点，将当前节点挂载到对应父节点的childs数组中
  data.forEach(item => {
    if (item.parentId === null) {
      tree.push(nodeMap.get(item.id));
    } else {
      const parentNode = nodeMap.get(item.parentId);
      if (parentNode) {
        parentNode.childs.push(nodeMap.get(item.id));
      }
    }
  });

  return tree;
}

// 使用示例
const treeResult2 = buildTreeWithMap(data);
console.log(treeResult2);

两种方法均可生成符合要求的树形结构，其中哈希表辅助的方法时间复杂度为O(n)，更适合处理大规模数据集。

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