算法：将列表还原为树状结构

Question

题目

给定一个列表，数据格式如下：

const list = [
  { pid: null, id: 1, data: "1" },
  { pid: 1, id: 2, data: "2-1" },
  { pid: 1, id: 3, data: "2-2" },
  { pid: 2, id: 4, data: "3-1" },
  { pid: 3, id: 5, data: "3-2" },
  { pid: 4, id: 6, data: "4-1" },
]

请你写一个函数，将列表转换成树状结构，转换后的格式如下：

[
  {
    pid: null,
    id: 1,
    data: '1',
    children: [
      {id: 2, pid: 1, data: '2-1'},
      {id: 3, pid: 1, data: '2-2'},
    ]
  }
]

解法

第一种：采用递归来做

function listToTree(list, id = null) {
  return list.reduce((acc, item) => {
    if (item.pid === id) {
      const children = listToTree(list, item.id)
      if (children.length) {
        item.children = children
      }
      return [...acc, item]
    }
    return acc
  }, [])
}

第二种：采用迭代，先用一个哈希表，以 id 为 key 存储对应的项，再申请一个 res 数组，找到根节点 push，同时根据 pid 找到哈希表的键插入 children。因为 JS 引用类型属性是共享的，所以对哈希表的项修改，也会反应在 res 数组中

function listToTree(list) {
    let res = []
    let map = {}
    for (let i = 0; i < list.length; i++) {
        map[list[i].id] = list[i]
        list[i].children = []
    }
    for (let i = 0; i < list.length; i++) {
        if (list[i].pid === null) {
            res.push(list[i])
        } else {
            map[list[i].pid].children.push(list[i])
        }
    }
    return res
}