练习题1-树形相关

[coolpail]

题目

以下数据结构中，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}
];
const result = convert(list, ...);

// 转换后的结果如下
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
            }
          ]
        }
      ]
    },
  ···
];

思路

1. 观察到id是按顺序排序的
2. 由题可知parentId是按id查找的
3. 所以id === index === parentId
4. 逆序操作，末尾添加到前面，然后删除当前

let len = list.length;
for (let i = len - 1; i >= 0; i--) {
    let item = list[i];
    let parentId = item.parentId;
    if (list[parentId - 1]) {
        if (list[parentId - 1].children) {
            list[parentId - 1].children.push(list[i]);
        } else list[parentId - 1].children = [list[i]];
        list.splice(i, 1);
    }
}