平层数组转树结构.md

平层数组转树结构

将一个平级的数组转换为数结构，如下：

// 输入内容
let input = [
  {
    id: 1,
    val: '学校',
    parentId: null,
  },
  {
    id: 2,
    val: '班级1',
    parentId: 1,
  },
  {
    id: 3,
    val: '班级2',
    parentId: 1,
  },
  {
    id: 4,
    val: '学生1',
    parentId: 2,
  },
  {
    id: 5,
    val: '学生2',
    parentId: 3,
  },
  {
    id: 6,
    val: '学生3',
    parentId: 3,
  },
];

// 输出内容
let output = [
  {
    id: 1,
    val: '学校',
    parentId: null,
    children: [
      {
        id: 2,
        val: '班级1',
        parentId: 1,
        children: [{ id: 4, val: '学生1', parentId: 2, children: [] }],
      },
      {
        id: 3,
        val: '班级2',
        parentId: 1,
        children: [
          { id: 5, val: '学生2', parentId: 3, children: [] },
          { id: 6, val: '学生3', parentId: 3, children: [] },
        ],
      },
    ],
  },
];

解题思路：

先遍历一遍数组，将数组的每个item项添加到哈希表中。

然后再遍历一次数组，每循环一次，判断当前节点是否有父节点

如果有父节点，则取出当前节点和当前节点的父节点，将当前节点插入到父节点的children中。

如果没有父节点，则表明当前节点是第一层次的节点，将其push到结果数组中。

function buildTree(list) {
  const map = new Map();
  const result = [];
  // 将每个item项存储在哈希表中
  for (let item of list) {
    map.set(item.id, { ...item, children: [] });
  }
  for (let item of list) {
    if (item.parentId === null) {
      result.push(map.get(item.id)); // 如果当前item项没有parentId则表示其为第一层级的节点，push到数组中
      continue;
    }
    const cur = map.get(item.id); // 当前节点
    const parent = map.get(item.parentId); // 父节点
    parent.children.push(cur); // 将当前节点插入到父节点children中
  }
  return result;
}