将一维数组转化成树

工作中遇到一个场景：有一个一维数组 Array

[
  {
    id: "0",
    name: "0",
    parentId: undefined,
  },
  {
    id: "1",
    name: "1",
    parentId: "0",
  },
];

每项具有如下结构：

interface Item {
  id: String;
  name: String;
  parentId: String;
}

需要转换成树形结构：

[
  {
    id: "0",
    name: "0",
    children: [
      {
        id: "1",
        name: "1",
        children: [],
      },
    ],
  },
];

思路

1. 用一个 Map 来存放每项的 id 和对应的对象（为什么不用 JS 的普通对象{}呢？因为 id 可能为 undefined，普通对象没法存，Map 才可以存）
2. 用一个数组 root 来存放树的所有根节点
3. 遍历原始数组，获取每个节点的 parentId

1. 如果有 parentId，说明有父节点，根据本节点的 parentId 从 Map 中找到父节点的对象，往里面的 children 中 push 本节点；
2. 如果没有 parentId，说明是根节点，把该节点 push 到 root 数组中

1. 最后返回 root 数组

实现

function solution(list) {
  const map = list.reduce((prev, cur) => {
    prev.set(cur.id, cur);
    return prev;
  }, new Map());
  const root = [];
  list.forEach((item) => {
    if (item.parentId !== undefined) {
      const parent = map.get(item.parentId);
      if (!parent) {
        return;
      }
      if (!parent.children) {
        parent.children = [];
      }
      parent.children.push(item);
    } else {
      root.push(item);
    }
  });
  return root;
}

测试用例

1. 有父节点，且父节点在一维数组中

[
  { id: 1, name: 1, parentId: 0 },
  {
    id: 0,
    parentId: undefined,
    name: 0,
  },
  { id: 11, name: 11, parentId: 1 },
  { id: 2, name: 2, parentId: 0 },
  { id: 22, name: 22, parentId: 2 },

1. 有父节点，但是父节点不在一维数组中

[
  { id: 1, name: 1, parentId: 0 },
  {
    id: 0,
    parentId: undefined,
    name: 0,
  },
  { id: 11, name: 11, parentId: 1 },
  { id: 22, name: 22, parentId: 2 },
];

1. 没有父节点

[
  { id: 1, name: 1 },
  {
    id: 0,

    name: 0,
  },
  { id: 11, name: 11 },
  { id: 22, name: 22 },
];

1. 数组为空

[];

运行结果

1. 有父节点，且父节点在一维数组中

2. 有父节点，但是父节点不在一维数组中

3. 没有父节点

4. 数组为空