数组转树形结构 - 翁先森的博客

这是一道面试题

要求如下，把 data 转换成树形结构

1
const data = [
2
  { id: "01", name: "张大大", pid: "", job: "项目经理" },
3
  { id: "02", name: "小亮", pid: "01", job: "产品leader" },
4
  { id: "03", name: "小美", pid: "01", job: "UIleader" },
5
  { id: "04", name: "老马", pid: "01", job: "技术leader" },
6
  { id: "05", name: "老王", pid: "01", job: "测试leader" },
7
  { id: "06", name: "老李", pid: "01", job: "运维leader" },
8
  { id: "07", name: "小丽", pid: "02", job: "产品经理" },
9
  { id: "08", name: "大光", pid: "02", job: "产品经理" },
10
  { id: "09", name: "小高", pid: "03", job: "UI设计师" },
11
  { id: "10", name: "小刘", pid: "04", job: "前端工程师" },
12
  { id: "11", name: "小华", pid: "04", job: "后端工程师" },
13
  { id: "12", name: "小李", pid: "04", job: "后端工程师" },
14
  { id: "13", name: "小赵", pid: "05", job: "测试工程师" },
15
  { id: "14", name: "小强", pid: "05", job: "测试工程师" },
16
  { id: "15", name: "小涛", pid: "06", job: "运维工程师" },
17
];

方法一（性能不是那么好）#

1
function transformArrToTree(arr) {
2
  /** 存储所有id对应项 */
3
  const idMap = {};
4

5
  const res = [];
6

7
  arr.forEach((item) => {
8
    const { id } = item;
9
    idMap[id] = item;
10
  });
11

12
  arr.forEach((item) => {
13
    const { pid } = item;
14

15
    if (!pid) {
16
      res.push(item);
17
    } else {
18
      const parent = idMap[pid];
19
      if (parent.children) {
20
        parent.children.push(item);
21
      } else {
22
        parent.children = [item];
23
      }
24
    }
25
  });
26

27
  return res;
28
}

1
计算时间: 0.235107421875 ms

方法二（好啊）#

维护一个 json 的 map，每一个 id 都有自己的 children 和本身的数据，把属于这个 id 的 pid 项都存入 children 数组，因为 json 的 map 都是对象，浅拷贝下，只要是属于这个对象的 children 数组都会是同一个

1
function transformArrToTree(arr) {
2
  const idMap = {};
3

4
  const res = [];
5

6
  arr.forEach((item) => {
7
    const { pid, id } = item;
8

9
    idMap[id] = {
10
      ...item,
11
      children: !idMap[id] ? [] : idMap[id].children,
12
    };
13

14
    if (!pid) {
15
      res.push(idMap[id]);
16
    } else {
17
      const parent = idMap[pid];
18
      if (!parent) {
19
        idMap[pid] = {
20
          children: [idMap[id]],
21
        };
22
      } else {
23
        parent.children.push(idMap[id]);
24
      }
25
    }
26
  });
27

28
  return res;
29
}

1
计算时间: 0.193115234375 ms