1、首先生成扁平数组

    // 生成随机数
    let random = (min, max) => parseInt(Math.random() * (max - min + 1) + min);
    // 生成扁平数组的方法，length可以控制生成的长度
    let createArr = length => {
      let arr = [];
      for (let i = 0; i < length; i++) {
        // 向数组内随机位置插入数据(打乱数组)，数据的pid也是随机的
        arr.splice(random(0, arr.length), 0, {
          id: i + 1,
          name: "我是第" + (i + 1) + "个",
          pid: random(0, i),
        });
      }
      return arr;
    };
    // 生成数组
    let arr = createArr(10000);
    // 检查生成的tree是否有遗漏
    let checkFn = arrs => {
      return JSON.stringify(arrs).match(/pid/gi).length;
    };

2、两种方法

1、递归写法，空间复杂度O(2^n)

    let toTree1 = (arrs, ids) => {
      let cutArr = [];
      let newArr = arrs.filter(i => {
        if (i.pid == ids) {
          return true;
        } else {
          cutArr.push(i);
          return false;
        }
      });
      newArr.map(i => {
        i.children = toTree1(cutArr, i.id);
      });
      return newArr;
    };
    console.time("递归方法总耗时");
    let res1 = toTree1(arr, 0);
    console.log("递归方法结果：", res1);
    console.timeEnd("递归方法总耗时");
    console.log("递归方法检查：", checkFn(res1, 0));

2、对象方法，空间复杂度O(n)（一次遍历，性能提升非常明显）

    let toTree2 = (arrs, ids) => {
      let newArr = [];
      let obj = {};
      for (let i = 0; i < arrs.length; i++) {
        let { id, pid } = arrs[i];
        if (!obj[id]) obj[id] = { children: [] };
        obj[id] = { ...arrs[i], children: obj[id].children };
        if (pid == ids) {
          newArr.push(obj[id]);
        } else {
          if (!obj[pid]) {
            obj[pid] = { children: [arrs[i]] };
          } else {
            obj[pid].children.push(arrs[i]);
          }
        }
      }
      return newArr;
    };
    console.time("对象方法总耗时");
    let res2 = toTree2(arr, 0);
    console.log("对象方法结果：", res2);
    console.timeEnd("对象方法总耗时");
    console.log("对象方法检查：", checkFn(res2, 0));

3、两种方法比较

当数组里有10000条数据的时候

微信图片_20220307203000.png