实现 convert 方法，把原始 list 转换成树形结构， 要求尽可能降低时间复杂度

类别：js / 日期：2023-05-10 / 浏览：293 / 评论：0

以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：

// 原始 list 如下
let list = [
  { id: 1, name: "部门 A", parentId: 0 },
  { id: 2, name: "部门 B", parentId: 0 },
  { id: 3, name: "部门 C", parentId: 1 },
  { id: 4, name: "部门 D", parentId: 1 },
  { id: 5, name: "部门 E", parentId: 2 },
  { id: 6, name: "部门 F", parentId: 3 },
  { id: 7, name: "部门 G", parentId: 2 },
  { id: 8, name: "部门 H", parentId: 4 },
];
const result = convert(list);

// 转换后的结果如下

let result = [
  {
    id: 1,
    name: "部门 A",
    parentId: 0,
    children: [
      {
        id: 3,
        name: "部门 C",
        parentId: 1,
        children: [
          {
            id: 6,
            name: "部门 F",
            parentId: 3,
          },
          {
            id: 16,
            name: "部门 L",
            parentId: 3,
          },
        ],
      },
      {
        id: 4,
        name: "部门 D",
        parentId: 1,
        children: [
          {
            id: 8,
            name: "部门 H",
            parentId: 4,
          },
        ],
      },
    ],
  },
];

function convert(list) {
  const res = [];
  const map = list.reduce((res, v) => ((res[v.id] = v), res), {});
  for (const item of list) {
    if (item.parentId === 0) {
      res.push(item);
      Continue;
    }
    if (item.parentId in map) {
      const parent = map[item.parentId];
      parent.children = parent.children || [];
      parent.children.push(item);
    }
  }
  return res;
}