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;
}