list2tree

一维数组转树结构的数组

这个算法应该是平时工作中很常用的一个算法了

第一种算法的的处理方式

1. 通过 reduce 归并方法生成一个 id 映射对应项的 map 数据.
2. 创建一个空数组 result 用于存新生成的 tree.
3. 通过遍历 arr 先把根节点找到（根节点没有 pid（parentId））
4. 有 pid 就是子孙节点，itemMap 就可以派上用场。通过它们的 pid 找自己的父级。找到后先判断父级有没有 children 属性，第一次需初始化处理，默认是空数组。然后再把自己添加到自己父级的children 属性中

第二种解法也是同样的逻辑，只是用了 Map 数据结构来存 id 和 对应项的映射关系。

let arr = [];
for (let i = 0; arr.length <= 100000; i += 1) {
  const id = i + 1;
  arr.push({
    id,
    name: `部门${id}`,
    pid: i,
  });
}
// [
//   { id: 1, name: '部门1', pid: 0 },
//   { id: 2, name: '部门2', pid: 1 },
//   { id: 3, name: '部门3', pid: 1 },
//   { id: 4, name: '部门4', pid: 3 },
//   { id: 5, name: '部门5', pid: 4 },
// ];

function arr2Tree1(arr = []) {
  console.time("timer1");
  if (!arr || !arr.length) return [];
  const result = [];
  const itemMap = arr.reduce((acc, item) => {
    acc[item.id] = item;
    return acc;
  }, {});

  for (const item of arr) {
    if (item.pid === 0) {
      result.push(item);
    } else if (item.id in itemMap) {
      const parent = itemMap[item.pid];
      parent.children = parent.children || [];
      parent.children.push(item);
    }
  }
  console.timeEnd("timer1");
  return result;
}

// const tree1 = arr2Tree1(arr);
// console.log('arr2Tree1', tree1);

let arr2 = [
  { id: 1, name: "部门1", pid: 0 },
  { id: 2, name: "部门2", pid: 1 },
  { id: 3, name: "部门3", pid: 1 },
  { id: 4, name: "部门4", pid: 3 },
  { id: 5, name: "部门5", pid: 4 },
  { id: 6, name: "部门5", pid: 5 },
];

function arr2Tree2(arr = []) {
  console.time("time2");
  if (!arr || !arr.length) return [];
  const result = [];
  const arrMap = new Map();

  arr.forEach((item) => {
    if (!arrMap.get(item.id)) {
      arrMap.set(item.id, item);
    }
  });

  for (const item of arr) {
    const { id, pid } = item;
    if (arrMap.get(pid)) {
      const parent = arrMap.get(pid);
      parent.children = parent.children || [];
      parent.children.push(item);
    } else {
      result.push(item);
    }
  }
  console.timeEnd("time2");
  return result;
}
console.log("arr2Tree2", arr2Tree2(arr));
console.timeEnd("time2");