第 88 题：实现 convert 方法，把原始 list 转换成树形结构，要求尽可能降低时间复杂度

Question

以下数据结构中，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
            }
          ]
        }
      ]
    },
  ···
];

Answer 1

两轮遍历，时间复杂度 O(n^2)

Answer 2

function convert(list) {
let result = [];
let len = list.length;
function searchChild(parent){
if(!parent)return;
if(!parent.id){
for (let i = 0; i < len; i++) {
if(list[i].parentId == 0){
var item = list.splice(i,1)[0];
i--;
len--;
item.children =[];
parent.push(searchChild(item));
}
}
}else{
for (let i = 0; i < len; i++) {
if(parent.id == list[i].parentId){
var item = list.splice(i,1)[0];
i--;
len--;
item.children =[];
parent.children.push(searchChild(item))
}
}
}
return parent
}
searchChild(result);
return result;
}
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}
];
convert(list)

Answer 3

面试题：
有如下格式的原始数据：
var obj ={
"title":"颜色",
"items":[
{
"title":"黄色",
"flag":true,
"child":{
"title":"尺码",
"items":[
{
"title":"XL",
"flag":true,
"child":{
"title":"形状",
"items":[
{
"title":"多边形",
"flag":true,
"skuId":1
},
{
"title":"方形",
"flag":false,
"skuId":2
}
]
}
},
{
"title":"M",
"flag":false,
"child":{
"title":"形状",
"items":[
{
"title":"方形",
"flag":false,
"skuId":3
}
]
}
}
]
}
},
{
"title":"红色",
"flag":false,
"child":{
"title":"尺码",
"items":[
{
"title":"M",
"flag":false,
"child":{
"title":"形状",
"items":[
{
"title":"方形",
"flag":false,
"skuId":3
}
]
}
}
]
}
}
]
}
效果如图：

@转换成可以实现联动的数据格式，暂不考虑库存问题，不需没有的属性变灰，切换属性，其他属性变化，有属性就显示，无的话就不显示

Answer 4

function convert(arr) {
  const obj = {}
  const res = []
  list.forEach(item => {
    obj[item.id] = item
  })
  list.forEach(item => {
    if (item.parentId !== 0) {
      obj[item.parentId]['children'] ? obj[item.parentId]['children'].push(item) : obj[item.parentId]['children'] = [item]
    } else {
      res.push(item)
    }
  })
  return res
}

Answer 5

基本思路：
使用Map保存id和对象的映射，循环list，根据parentId在Map里取得父节点，如果父节点有children属性，就直接push当前的子节点，如果没有就添加children属性，最后遍历一遍list把parentId===0的节点取出来。

const convert = list => {
  let map = new Map();
  let result = []
  list.forEach(el => {
    map.set(el.id, el);
  });
  list.forEach(el => {
		let parent = map.get(el.parentId);
		if (!parent) {
			// parentId === 0
			el.children = []
			return 
		}
    if (parent.hasOwnProperty('children')) {
      parent.children.push(el);
    } else {
      parent['children'] = [];
      parent.children.push(el);
    }
	});
	for (let i = 0; i < list.length; i++) {
		const el = list[i];
		if (el.parentId === 0) {
			result.push(el)
		}
	}
	return result
};
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 }
];
convert(list)

Answer 6

function convert(list) {
	const res = []
	const map = list.reduce((res, v) => (res[v.id] = v, res), {})
	for (const item of list) {
		if (item.parentId === 0) {
			res.push(item)
			continue
		}
		if (item.parentId in map) {
			const parent = map[item.parentId]
			parent.children = parent.children || []
			parent.children.push(item)
		}
	}
	return res
}

时间复杂度O(n)