实现 convert 方法，把原始 list 数组转换成树形结构

[liangbus]

以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门
现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：

// 原始 list 如下
let list =[
    {id:1,name:'部门A',parentId:0},
    {id:2,name:'部门B',parentId:0},
    {id:3,name:'部门C',parentId:1},
    {id:4,name:'部门D',parentId:1},
    {id:5,name:'部门E',parentId:2},
    {id:6,name:'部门F',parentId:3},
    {id:7,name:'部门G',parentId:2},
    {id:8,name:'部门H',parentId:4}
];

// 转换后的结果如下
let result = [
    {
      id: 1,
      name: '部门A',
      parentId: 0,
      children: [
        {
          id: 3,
          name: '部门C',
          parentId: 1,
          children: [
            {
              id: 6,
              name: '部门F',
              parentId: 3
            }, {
              id: 16,
              name: '部门L',
              parentId: 3
            }
          ]
        },
        {
          id: 4,
          name: '部门D',
          parentId: 1,
          children: [
            {
              id: 8,
              name: '部门H',
              parentId: 4
            }
          ]
        }
      ]
    },
];

拿到这个问题，开始把问题给复杂化了，想着要多少遍循环，实际上，O(n) 即可，利用了对象引用的特性，如下：

function convert(list) {
  // 将初始数组，转换成一个 map
  const map = list.reduce((res, cur) => {
    res[cur.id] = cur
    return res
  }, {})
  const res = []
  for(let item of list) {
    // 将根节点推到结果中去
    if (item.parentId === 0) {
      res.push(item)
      continue
    }
    // 检查对应的 parentId，将其添加到对应节点下的 children
    // 因为所有的节点，都在 map 里面作为一级结构，所以无需多次遍历
    if(item.parentId in map) {
      const parent = map[item.parentId]
      parent.children = parent.children || []
      parent.children.push(item)
    }
  }
}