js手写题之数组转化为树

[jiefancis]

题意

将
var arr = [
    {id: 4, name: '部门4', pid: 3},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 5, name: '部门5', pid: 4},
    {id: 1, name: '部门1', pid: 0},
]

转换为

[
    {
        "id": 1,
        "name": "部门1",
        "pid": 0,
        "children": [
            {
                "id": 2,
                "name": "部门2",
                "pid": 1,
                "children": []
            },
            {
                "id": 3,
                "name": "部门3",
                "pid": 1,
                "children": [
                    // 结果 ,,,
                ]
            }
        ]
    }
]

常规解法

function convertArr2Tree(arr) {
      var res, map = {};
      // 将所有元素的 id 跟 item作为一个键值对
      for(let item of arr) {
          if(item.pid === 0) { res = item }
          map[item.id] = item;
      }
      // 再次遍历，根据pid匹配找到当前元素对应的父级，完成数据格式的转换
      for(let item of arr) {
          if(map[item.pid]) {
              map[item.pid].children = map[item.pid].children ? map[item.pid].children.concat(item) : [item];
          }
      }

      return res
  }

O(n)解法

通过 id 跟 pid匹配map，数据转换的格式的不同，

var arr = [
  {id: 4, name: '部门4', pid: 3},
  {id: 2, name: '部门2', pid: 1},
  {id: 3, name: '部门3', pid: 1},
  {id: 5, name: '部门5', pid: 4},
  {id: 1, name: '部门1', pid: 0},
]
arrayToTree(arr)
function arrayToTree(items) {
const result = [];   // 存放结果集
const itemMap = {};  // 
for (const item of items) {
  const id = item.id;
  const pid = item.pid;

  // 根据 id 匹配，每一个item都添加children属性
  const treeItem = {
    ...item,
    children: itemMap[id]?.children || []
  }

  itemMap[id] = treeItem;

  if (pid === 0) {
    result.push(treeItem);
  } else {
   // 根据 pid 匹配，说明当前元素是itemMap[pid]的子元素。itemMap[pid]是itemMap[id]初始化而来
    if (!itemMap[pid]) {
      itemMap[pid] = {
        children: [],
      }
    }
    itemMap[pid].children.push(treeItem)
  }
}
console.log('itemMap', itemMap)
return result;
}