Daily-Interview-Question
Daily-Interview-Question copied to clipboard
Published
20 hours ago •
Advanced-Frontend
Advanced-Frontend
第 88 题：实现 convert 方法，把原始 list 转换成树形结构，要求尽可能降低时间复杂度
以下数据结构中，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
}
]
}
]
},
···
];
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)
基本思路： 使用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)
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
}
面试题：
有如下格式的原始数据：
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
}
]
}
}
]
}
}
]
}
效果如图：
@转换成可以实现联动的数据格式，暂不考虑库存问题，不需没有的属性变灰，切换属性，其他属性变化，有属性就显示，无的话就不显示
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)
两轮遍历，时间复杂度 O(n^2) :joy:
function convert(arr) {
let tree = [];
arr.map((it, idx, array) => {
let parent = it.parentId;
if (parent === 0) { // 根节点
tree.push(it);
} else {
array.map(item => {
if (item.id === parent) {
if (!item.children) {
item.children = [];
}
item.children.push(it);
}
});
}
});
return tree;
}
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 }
];
function convert(array) {
let reslutArray = array.filter((item) => {
let children = array.filter((child) => {
return item.id === child.parentId
})
item.children = children
return item.parentId === 0
})
return reslutArray
}
let res = convert(list)
console.log(res)
const convert = (list) => { const result = [];
list.map(item => {
if (item.parentId) {
if (!list[item.parentId - 1]['children']) {
list[item.parentId - 1]['children'] = [];
}
list[item.parentId - 1]['children'].push(item);
}
else {
result.push(item)
}
});
return result
}
两轮遍历，时间复杂度 O(n^2) 😂
function convert(arr) { let tree = []; arr.map((it, idx, array) => { let parent = it.parentId; if (parent === 0) { // 根节点 tree.push(it); } else { array.map(item => { if (item.id === parent) { if (!item.children) { item.children = []; } item.children.push(it); } }); } }); return tree; }
大佬看看我的？
function convert(list) {
var obj = {};
var result = [];
list.map(el => {
obj[el.id] = el;
})
for(let i=0, len = list.length; i < len; i++) {
let id = list[i].parentId;
if(id == 0) {
result.push(list[i]);
continue;
}
if(obj[id].children) {
obj[id].children.push(list[i]);
} else {
obj[id].children = [];
obj[id].children.push(list[i]);
}
}
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);
@
function convert（list）{ const res = [] const map = list。减少（（RES，v）=>（RES [ v。ID ] = V，RES），{}） 为（const的 项目 的列表）{ 如果（项目。parentId的 === 0）{ 水库。推（项目） 继续 } 如果（项目。parentId的 在地图）{ const的 父 =地图[ 项目。parentId ] 父母。孩子 = 父母。孩子们 || [] 父母。孩子们。推（项目） } } 返回资源 }时间复杂度为O（n）
这个算不上O(n)吧
const convert = (list) => {
if (!Array.isArray(list)) {
return []
}
list.forEach((v) => {
const index = list.findIndex((_l) => {
return v.parentId == _l.id
});
if (index == -1) {
return
}
list[index].child = list[index].child || []
list[index].child.push(v);
v.hide = true;
});
return list.filter(v => { return !v.hide });
}
难度的话O(n*2)左右
@
function convert（list）{ const res = [] const map = list。减少（（RES，v）=>（RES [ v。ID ] = V，RES），{}） 为（const的 项目 的列表）{ 如果（项目。parentId的 === 0）{ 水库。推（项目） 继续 } 如果（项目。parentId的 在地图）{ const的 父 =地图[ 项目。parentId ] 父母。孩子 = 父母。孩子们 || [] 父母。孩子们。推（项目） } } 返回资源 }时间复杂度为O（n）
这个算不上O(n)吧
这就是O(n)啊, 第一次遍历生成哈希表扫描了一次，然后再扫描了一次list，总共进行了2n次操作，时间复杂度是O(2n) = O(n)
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) 执行了一次map,一次for，应该是o(n^2)了吧
基于DFS来写
function convert(source, parentId = 0){
let trees = [];
for (let item of source) {
if(item.parentId === parentId) {
let children = convert(source, item['id']);
if(children.length) {
item.children = children
}
trees.push(item);
}
}
return trees;
}
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);
function convert(list){ let map={}; let newArr=[]; for(var i=0;i<list.length;i++){ map[list[i].id]=list[i] } for(var i=0;i<list.length;i++){ if(list[i].parentId in map){ map[list[i].parentId].children=[]; map[list[i].parentId].children.push(list[i]) } if(map[list[i].parentId] && 'children' in map[list[i].parentId]){ newArr.push(map[list[i].parentId]) } } return newArr }
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) 执行了一次map,一次for，应该是o(n^2)了吧
如果这两个是嵌套循环就是n^2, 代码里面明显是两次，而不是嵌套的
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) 执行了一次map,一次for，应该是o(n^2)了吧
如果这两个是嵌套循环就是n^2, 代码里面明显是两次，而不是嵌套的
for of里面不是包括了for in 吗？
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) 执行了一次map,一次for，应该是o(n^2)了吧
如果这两个是嵌套循环就是n^2, 代码里面明显是两次，而不是嵌套的
for of里面不是包括了for in 吗？ 哪有for in，item.parantId in map，在一个对象里面查找一个key是O(1)的操作
一次循环解决
function convert(list) {
const cache = new Map()
return list.reduce((res, cur) => {
const { id, parentId } = cur
const item = { ...cur }
if (parentId === 0) {
res.push(item)
} else {
const itemCache = cache.get(parentId)
!itemCache.children && (itemCache.children = [])
itemCache.children.push(item)
}
cache.set(id, item)
return res
}, []);
}
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) 执行了一次map,一次for，应该是o(n^2)了吧
如果这两个是嵌套循环就是n^2, 代码里面明显是两次，而不是嵌套的
for of里面不是包括了for in 吗？ 哪有for in，item.parantId in map，在一个对象里面查找一个key是O(1)的操作 这个map看错了，哈哈哈
用递归试试
function convert(array , parentId=0){
let result = []
array.forEach((item,index)=>{
if(item.parentId === parentId){
let children = convert(array,item.id);
if(children.length>0){
item.children = children ;
}
result.push(item);
}
})
return result;
}
covert(lists: any[]): any[] {
const findItem = (id: number) => {
return lists.find(item => item.id === id);
};
const result = [];
lists.map(item => {
if (item.parentId === 0) {
result.push(item);
} else {
const target = findItem(item.parentId);
target.children = target.children || [];
target.children.push(item);
}
});
return result;
}
看了大佬们写的用map要好一些
function convert(list) {
let m = new Map()
return list.reduce((pre,cur)=>{
m.set(cur.id,cur)
let parent = m.get(cur.parentId)
if( parent){
(parent.children || (parent.children = [])).push(cur)
return pre
}
return [...pre,cur]
},[])
}
这么多人写了我就随便再写个吧，时间复杂度 O(n)
/*
转换成树形结构
思路：
1、构造一个id与对象的对应关系
2、循环变价原数组，将item放在指定的parent之下
3、循环字典，找出parentId === 0的对象即可
****一共3遍遍历3*O(n)*****
*/
function convert (list) {
let arr = [];
let dict = {};
list.forEach(item => {
dict[item.id] = item;
})
list.forEach(item => {
if(item.parentId) {
let children = dict[item.parentId].children;
if (children) {
dict[item.parentId].children.push(item)
} else {
dict[item.parentId].children = [item];
}
}
})
for(let key in dict) {
if(dict[key].parentId === 0) {
arr.push(dict[key])
}
}
return arr;
}
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}
];
let res = convert(list);
console.log(res)
const convert = (list) => {
const obj = {}
while (list.length) {
let temp = list.shift()
obj[temp.id] = temp
if(obj[temp.parentId]) {
obj[temp.parentId]['children'] = (obj[temp.parentId]['children'] || []).concat(temp)
}
}
return [...Object.values(obj)].filter(item => item.parentId === 0)
}
const res = convert(list)
加了个map记录parent的路径，这个循环一次。
const convertData2Tree = (dataArr) => {
let nodesMap = {};
let result = [];
dataArr.forEach(element => {
let { id, parentId } = element;
if (parentId === 0) {
result.push(element);
nodesMap[id] = result[result.length - 1];
} else {
let parent = nodesMap[parentId];
if (!parent.children) {
parent.children = [];
}
parent.children.push(element);
nodesMap[id] = nodesMap[parentId].children[parent.children.length - 1];
}
});
return result;
};
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)
这个的时间复杂度为什么不是2*O(n)
```js 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)
const map = list.reduce((res, v) => (res[v.id] = v, res), {})生成通过id索引的map，但是(res, v) => (res[v.id] = v, res)这样的箭头函数，我找不到解释，(res[v.id] = v, res)，加个逗号是在括号内另起一行，返回accumulator：res吗？不懂
感觉上边都没有考虑原数据，都是把原数组改变掉了。我这里用了比较简单的规律： function convert(list){ let arr = JSON.parse(JSON.stringify(list)); for(let i = list.length - 1; i >= 0 ;i--){ if(arr[i].parentId - 1 < 0){ continue; } if(arr[arr[i].parentId - 1].children){ arr[arr[i].parentId -1].children.push(arr[i]) }else{ arr[arr[i].parentId -1].children = [arr[i]] } arr.splice(i,1); } return arr }
function convert(list) {
const map = {};
// 不修改数据源，可省略
// const copy = [].concat(list).map(li => ({...li}));
const result = [];
copy.map(li => {
const {id, parentId} = li;
map[id] = li;
if (parentId === 0) result.push(li);
else if (map[parentId]) {
if (!map[parentId].children) map[parentId].children = [];
map[parentId].children.push(li);
}
});
return result;
}
时间复杂度为 O(n)
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 }
];
function convert(list, parentId = 0) {
let result = [];
for (let i = 0; i < list.length; i++) {
let item = list[i];
if (item.parentId === parentId) {
let newItem = {
...item,
children: convert(list, item.id)
};
result.push(newItem);
}
}
return result;
}
console.log(convert(list));
`const 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} ];
function convert(arr){
const root = [];
if(arr.length === 0){
return root;
}
const ids = [],
childrens = [];
arr.forEach(item => {
ids.push(item.id);
});
arr.forEach(item => {
if(ids.includes(item.parentId)){
childrens.push(item);
}else{
root.push(item);
}
});
convert(childrens).forEach(item => {
root.forEach(rootEl => {
if(rootEl.id === item.parentId){
rootEl.children = (rootEl.children && rootEl.children.concat([item])) || [item];
}
});
});
return root;
}
console.log(convert(list));`
function convert(list) { for(let i=list.length-1;i>=0;i--){ let pid =list[i].parentId; if(pid>0){ if(!list[pid-1].children){ list[pid-1].children=[]; } list[pid-1].children.push(list[i]) list.splice(i,1) }
}
console.log(list); }
function convert(list) {
for (let i = 0; i < list.length; i++) {
list[i].children = []
for (let j = i + 1; j < list.length; j++) {
if (list[i].id === list[j].parentId) {
list[i].children.push(list[j])
list.splice(j, 1)
j = i
}
}
}
return list.map((item) => {
const {
id,
name,
parentId,
children
} = item
if (children.length > 0) {
return item
}
return {
id,
name,
parentId
}
})
}
console.log(convert(list))
function convert(list, parent) {
return list.filter(item => {
if (item.parentId === parent) {
item.children = convert(list, item.id)
return true
}
})
}
let result=convert(list,0)
加了个参数，不知道这种写法是否符合要求
function convert (list) { var obj = {}, res = [] list.forEach(v => obj[v.id] = v) list.forEach(v => { if (!v.parentId) res.push(v) if (v.parentId in obj) { var a = obj[v.parentId] console.log(a) Array.isArray(a.child)? a.child.push(v): a.child = [v] } }) console.log(res) }
解释下list.reduce((res, v) => (res[v.id] = v, res), {}) reduce接受2个参数 最后面的 {}当做第一次reduce的res 每次循环，把 {} 添加一个key，然后value就是v 至于 => (res[v.id] = v, res)这个东东，纯属是为了写起来简便 箭头函数后面只有一个代码块的话，可以省略{}和return ，所以每次循环返回 的就是(res[v.id] = v, res) 这时候，你试一下 var a = (1, 2, 6);console.log(a);你会发现a是6 所以返回的返回 的就是(res[v.id] = v, res)其实就是res，并且作为下一次循环调用接受的第一个参数
推荐这种写法，大家更容易看懂些 list.forEach(v => obj[v.id] = v)
function convert (arr) {
const map = {}
let tree = []
let level
arr.forEach(item => {
if (!map[item.parentId]) {
map[item.parentId] = []
}
map[item.parentId].push(item)
if (!map[item.id]) {
map[item.id] = []
}
item.child = map[item.id]
if (!level && level !== 0) {
tree.push(item)
level = item.parentId
} else if (level == item.parentId) {
tree.push(item)
} else if (level > item.parentId) {
tree = [item]
level = item.parentId
}
})
return tree
}
一次循环搞定，将树节点的child与map的属性都指向同一个数组首地址，数组每次更新自然更新child内容，然后再将同一级的顶层节点加入到最终的数组中
function convert(list){ let map = {}; let origin = []; for(let i = 0; i < list.length; i++){ let id = list[i].id; let parentId = list[i].parentId; if(parentId == 0){ let obj = Object.assign({},list[i]); let test = map[id] || []; obj.children = test; origin.push(obj); map[id] = test; } else { let obj = Object.assign({},list[i]); let children = map[parentId] || []; let test = map[id] || []; children.push(obj); obj.children = test; map[id] = test; } } console.log(JSON.stringify(origin)); }
把树状结构转换为扁平化。根据map映射把有children的引用属性保留。通过map快速在children后面追追加数据
const list2Tree = (list) => {
let root = { id: 0, name: 'root', children: [] }
let cache = { 0: root };
while(list.length) {
let cur = list.shift()
if (cache[cur.parentId]) {
cache[cur.parentId].children ? cache[cur.parentId].children.push(cur) : cache[cur.parentId].children = [cur]
} else {
list.push(cur)
}
if (!cache[cur.id]) cache[cur.id] = cur
}
console.log(cache[0].children)
console.log('equal', JSON.stringify(cache[0].children) === JSON.stringify(origin))
}
利用Array的高阶函数filter来是实现。
function convert(list){
const tree=list.filter((parent)=>{
const temp=list.filter((child)=>{
return child.parentId===parent.Id;
})
temp.length&&(father.children=temp);
return parent.parentId===0;
})
return tree;
}
```js 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)
const map = list.reduce((res, v) => (res[v.id] = v, res), {})生成通过id索引的map，但是(res, v) => (res[v.id] = v, res)这样的箭头函数，我找不到解释，(res[v.id] = v, res)，加个逗号是在括号内另起一行，返回accumulator：res吗？不懂
(res[v.id] = v, res)相当于执行了以下代码
{
res[v.id] = v;
return res;
}
const convert = (list, root = 0) => {
let maping = {};
for (let item of list) {
let children = item;
if (maping[item.id] ) {
// 补全信息
children = maping[item.id] = {
id: item.id,
name: item.name,
parentId: item.parentId,
children: maping[item.id].children
};
} else {
maping[item.id] = children;
}
if (maping[item.parentId]) {
maping[item.parentId].children || (maping[item.parentId].children = []);
} else {
maping[item.parentId] = { children: [] }
}
maping[item.parentId].children.push(children);
}
return maping[root].children;
}
时间复杂度O(n)
基于DFS来写
function convert(source, parentId = 0){ let trees = []; for (let item of source) { if(item.parentId === parentId) { let children = convert(source, item['id']); if(children.length) { item.children = children } trees.push(item); } } return trees; } 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);
你这个时间复杂度 比O(n^2) 还n2 .。。。难受
const train = (list) => {
list.forEach((item, index) => {
list.forEach((item) => {
if(item.parentId == list[index].id){
list[index].children = list[index].children || []
list[index].children.push(item)
}
})
})
list = list.filter((item) => !item.parentId)
return list
}
let result2 = train(list)
console.log(result2, "result2")
const listToTree2 = (myId, PId, list): Array<any> => {
let result = [];
let map = list.reduce((p, i) => {
p[i[myId]] = i;
return p;
}, {});
for (let item of list) {
if (!item[PId]) {
result.push(item);
}
if (Reflect.has(map, item[PId])) {
let parent = map[item[PId]];
parent.children = parent.children || [];
parent.children.push(item);
}
}
return result;
};
console.log(listToTree2('ids', 'parentId', allList));
学习了, 又学到了新姿势, 棒~
方法1：
function convert (list) {
let res = [];
let map = Object.create(null);
list.forEach(item => {
map[item.id] = item;
if (!item.parentId) res.push(item);
});
list.forEach(item => {
if (item.parentId)
(map[item.parentId].children = map[item.parentId].children || [])
.push(item);
});
return res;
}
方法2：
function convert (list) {
let item, id, parent, parentId;
let map = {};
let res = [];
for (item of list) {
id = item.id;
if (map[id]) { // 之前被当做父元素了，现在用真正的元素替换之前加的占位符
item.children = map[id].children;
}
map[id] = item;
parentId = item.parentId;
if (parentId) { // 处理一下父元素，暂时没有的加个占位符
if ((parent = map[parentId])) {
(parent.children = parent.children || []).push(item);
} else {
map[parentId] = { children: [item] };
}
} else res.push(item);
}
return res;
}
借助hashmap保存节点,遍历一次数组即可
function convert(arr) {
let node, res = [], map = new Map();
while (arr.length) {
node = arr.shift();
node.children = [];//保证结构的一致性,但有副作用,导致最末端的节点也会有一个children属性
map.set(node.id, node);
if (node.parentId === 0) res.push(node)
else map.get(node.parentId).children.push(node)
}
return res;
}
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)
这个不能算时间复杂度n吧。毕竟你上面reduce已经算一圈了。
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 convert = list => {
const map = new Map(),
res = []
// 使用map保存list的id映射
list.forEach(ele => map.set(ele.id, ele))
list.forEach(ele => {
if (ele.parentId === 0) {
res.push(ele)
} else {
if (map.has(ele.parentId)) {
const parent = map.get(ele.parentId)
parent.children = parent.children || []
parent.children.push(ele)
}
}
})
return res
}
console.log(convert(list))
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)
麻烦能解释下(res, v) => (res[v.id] = v, res)箭头后面直接跟圆括号是什么用法，以及这里面是怎么执行的吗？
function covert(list) {
let result = [];
let map = {};
/*
map用来存储自己所处的位置，比如自己所处的位置为 [0,0,0] 代表自己存在与 最外层的第0个，下面的children的第一个元素的children的第一个。这样每次循环list的时候判断parentId就能直接拿到应该放在哪
*/
list.forEach(item => {
if (map[item.parentId]) {
// 如果map中存在该parentId所处的位置，那么需要将当前item放入到该parentId的childe中
let child;
map[item.parentId].forEach(item => {
if (!child) {
child = result[item];
} else {
child = child.children[item];
}
});
if (child.children) {
child.children = [...child.children, item];
} else {
child.children = [item];
}
map[item.id] = [map[item.parentId], child.children.length-1];
} else {
result.push(item);
map[item.id] = [result.length-1];
}
})
return result;
}
时间复杂度O(n)
正儿八经的O(n)，好多假O(n)啊
function convert (list, topid = 0) {
const result = [];
let map = {};
list.forEach(item => {
const { id, parentId } = item;
if (parentId === topid) {
result.push(item);
} else {
map[parentId] = map[parentId] || [];
map[parentId].push(item);
}
item.children = item.children || map[id] || (map[id] = [])
})
map = null;
return result;
}
方法一：
function convert(list){
for(let i = 0 ; i < list.length; i++) {
let current = list[i]
if (current.parentId) {
let parent = list.find(item => item.id === current.parentId)
parent.children = parent.children || []
parent.children.push(current)
}
}
return list.filter(item => item.parentId === 0)
}
方法二，参考上面大兄弟的答案 使用map
function convert2(list) {
let map = {}
let res = []
for (let i = 0; i < list.length; i++) {
map[list[i].id] = list[i]
}
for (let i = 0; i < list.length; i++) {
let cur = list[i]
if (!cur.parentId) {
res.push(cur)
continue
}
if (map[cur.parentId]) {
map[cur.parentId].children = map[cur.parentId].children || []
map[cur.parentId].children.push(cur)
}
}
return res
}
function convert(list) { let m = new Map() return list.reduce((pre,cur)=>{ m.set(cur.id,cur) let parent = m.get(cur.parentId) if( parent){ (parent.children || (parent.children = [])).push(cur) return pre } return [...pre,cur] },[]) }这么多人写了我就随便再写个吧，时间复杂度 O(n)
你这种数据如果有乱序就不能用了
let list =[
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4},
{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},
];
console.log(convert(list));
看来最少都要两次循环 @307590317
@dongj0316 的是一次, 请问各位如果把楼主的题目加个要求排序, 那怎么做才是最好的呢?
@yygmind 博主有这道题吗?
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 }
121 道题重复了
//写法精简 const fn_10 = (list, id = 0) => list.filter(item => item.parentId === id).map(item => ({ ...item, children: fn_10(list, item.id) }))
//性能优秀（只遍历两遍） const fn_11 = (list) => { const obj = list.reduce((pre,cur)=>{ pre.hasOwnProperty(cur.parentId+'') ? pre[cur.parentId].push(cur) : pre[cur.parentId]=[cur]; return pre; },{}); const fn = (arr) => { arr = arr || []; return arr.map(item => ({ ...item, children: fn(obj[item.id]) })) } return fn(obj[0]); }
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) 执行了一次map,一次for，应该是o(n^2)了吧 俩次循环没嵌套在一起，虽然是2n，但是n无限大时就是O(n)
function convert (list) {
let obj = list.reduce((pre, item) => {
pre[item.parentId] = pre[item.parentId] || []
pre[item.parentId].push(item)
return pre
}, {})
let arr = []
for (let k in obj) {
let item = list.find(item => item.id === +k)
if (item) {
item.children = obj[k]
delete obj[k]
} else {
arr.push(obj[k])
}
}
return arr
}
function convert(list) {
let map = {};
list.forEach(v => {
if(map[v.parentId]) {
map[v.parentId].push(v);
}else {
map[v.parentId] = [v];
}
})
list.forEach(v => {
if(map[v.id]) {
v.children = map[v.id];
}
})
console.log(list)
}
清新脱俗
const convert = (items, id = 0, link = 'parentId') => items.filter(item => item[link] === id).map(item => ({ ...item, children: convert(items, item.id) }));
利用js对象数据类型为引用类型的性质，时间复杂度只需要o(n)遍历数据对象一次即可将普通数组数据转化为tree状数据；基础数据类型可以乱序；
const 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 }
];
/*生成树型对象*/
function convert(data, parentId, id) {
parentId = parentId || 'parentId';
id = id || 'id';
data.forEach(function (item) {
delete item.children;
});
const map = {};
data.forEach(function (item) {
map[item[id]] = item;
});
const res = [];
data.forEach(function (item) {
const parent = map[item[parentId]];
if (parent) {
(parent.children || (parent.children = [])).push(item);
} else {
res.push(item);
}
});
return res;
}
console.log(convert(list))
function convert(list) {
const arr = [];
let map = list.reduce((a, b)=>{a[b.id] = b; return a}, {});
for(let key in map){
var item = map[key];
if(item.parentId === 0){
arr.push(item);
}else{
var parent = map[item.parentId];
(parent.children || (parent.children = [])).push(item);
}
}
return arr;
}
let tanslate = list => {
// 先建立每一项的id和数据的对应关系
let map=new Map();
list.map(el=>{map.set(el.id,el)});
let res=[];
for(let item of list){
// 把根节点存进数组
if(!item.parentId){
res.push(item);
continue;
}
//遍历过程中，找到item的parentId，在映射表中直接取出这个元素，把item推进它的children。
if(map.has(item.parentId)){
let parent=map.get(item.parentId);
parent.children?parent.children.push(item):parent.children=[item];
}
}
console.log(res)
}
var convert = function(arr) {
if (!arr || arr.length === 0) {
return null;
}
let res = [];
let hash = new Map();
arr.forEach((item) => {
hash.set(item.id, item);
})
arr.forEach((item) => {
let id = item.parentId;
if(id === 0) {
res.push(item);
} else {
let parent = hash.get(id);
parent['children'] = item;
}
})
return res;
};
刚好昨天总结了一番，我看楼上都有，总结一下：
- 最简单的写法：filter+map+递归
const nest = (items, code = 0, link = 'parentCode') { // code就是老爸的code，大型认爹现场
return items
.filter(v => v[link] === code)
.map(v => ({ ...v, children: nest(items, v.code) }))
}
- for循环+递归
const nest = (items, code = 0, link = 'parentCode') {
const res = []
for (let v of items) {
if (v[link] === code) {
res.push({
...v,
children: nest(items, v.code)
})
}
}
return res
}
- 最快的写法：for循环+map（空间换时间）
const nest = (items, code = 0, link = 'parentCode') {
const res = []
const map = items.reduce((total, cur) => {
cur.children = []
total[cur.code] = cur
return total
}, {}) // 定义所有数据的map
for (let v of items) {
if (v[link] === code) {
res.push(v)
continue
}
let a = map[v[link]]
if (a) a.children.push(v)
}
return res
}
- 运行时间大概对比
function convert (list) {
// 按照parentId 分组，得到相同父节点的数据
var groupByParentId = {}
list.forEach(item => {
if(groupByParentId[item.parentId] == undefined) {
groupByParentId[item.parentId] = [item]
} else {
groupByParentId[item.parentId].push(item)
}
})
// 根据id映射数据
var idMap = {}
list.forEach(item => {
idMap[item.id] = item
})
// 遍历数据，id 跟 parentId 分组相同的说明该节点是有子节点的，子节点便是按父节点分组的数据
list.forEach(item => {
if(groupByParentId[item.id]) {
item.children = groupByParentId[item.id]
}
})
// 返回父节点为0的分组数据
return groupByParentId[0]
}
O(n)
function convert(list) {
let result = []
let map = new Map()
list.forEach(item => {
map.set(item.id, item)
item.children = []
if (item.parentId === 0) {
result.push(item)
}
})
list.forEach(item => {
let parentId = item.parentId
if (parentId !== 0) {
map.get(parentId).children.push(item)
}
})
return result
}
function convert(list) {
return list.reduce((result, item) => {
item.child = []
result[item.id] = item;
result[item.parentId].child.push(item)
return result
}, {'0': {child: []}})[0].child
}
套了两层reduce 不知道这个 复杂度是 多少了..... O(n方)吗?
const convert = list => {
let resultArray = list.reduce((acc,cur) => {
cur.children = list.reduce((total,item) => {
if (item.parentId === cur.id) {
total.push(item)
}
return total
},[])
if (cur.parentId === 0) {
acc.push(cur)
}
return acc
},[])
return resultArray
}
两轮遍历，时间复杂度 O(n^2) 😂
function convert(arr) { let tree = []; arr.map((it, idx, array) => { let parent = it.parentId; if (parent === 0) { // 根节点 tree.push(it); } else { array.map(item => { if (item.id === parent) { if (!item.children) { item.children = []; } item.children.push(it); } }); } }); return tree; }
为什么 第二个map遍历会让tree也改变了
function fn2 (list) {
const obj = {};
list.forEach((item) => {
const key = item.parentId;
const id = item.id;
obj[key] = obj[key] || [];
obj[key].push(item);
obj[id] = obj[id] || [];
item.children = obj[id];
});
list.forEach((item) => {
if (item.children && !item.children.length) delete item.children;
});
return obj['0'];
}
function convert(list){
let res = [];
let map = new Map();
list.map(item => {
map.set(item.id, item);
if(item.parentId == 0){
res.push(item);
}else{
let current = map.get(item.parentId);
current.children = current.children || [];
current.children.push(item);
}
});
return res;
}
function convert(list, parentId){
let tree = []
let temp
for(let i=0; i<list.length; i++){
if(list[i].parentId === parentId){
let obj = list[i]
temp = convert(list, list[i].parentId)
if(temp.length>0){
temp.children = obj
}
tree.push(obj)
}
}
return tree
}
` function fn(data, pid) {
let result = [], temp;
for (let i = 0; i < data.length; i++) {
if (data[i].parentId == pid) {
const obj = {id: data[i].id, name:data[i].name};
temp = fn(data, data[i].id);
if (temp.length > 0) {
obj.children = temp;
}
result.push(obj);
}
}
return result;
} `
function convert(list){
let map = new Map()
for(let i of list){
map.set(i.id, i)
}
let res = []
map.forEach(value=>{
if(!value.parentId){
res.push(value)
}else{
let item = map.get(value.parentId)
item.children = item.children || []
item.children.push(value)
}
})
return res
}
const convert = (list) => {
const result = []
for (let i = 0, len = list.length; i < len; i++) {
const node = list[i]
if (node.parentId === 0) {
result.push(node)
} else {
let flag = true
let tempList = result
while (flag) {
for (let i = 0, len = tempList.length; i < len; i++) {
if (tempList[i].id === node.parentId) {
// 找到
if (!tempList[i].children) {
tempList[i].children = []
}
tempList[i].children.push(node)
flag = false
break
}
}
if (flag) {
let tempL = []
for (let i = 0, len = tempList.length; i < len; i++) {
tempL.push(...tempList[i].children)
}
tempList = [...tempL]
}
}
}
}
return result
}
function convert(list) {
const map = {}
const res = []
list.forEach(item => {
map[item.id] = {
...item,
children: []
}
})
list.forEach(item => {
const pId = item.parentId
if (map[pId]) {
map[pId].children.push(map[item.id])
}
if (pId === 0) {
res.push(map[item.id])
}
})
return res
}
function convert(list = []){
const map = new Map();
// 转成Map, id作为key
for(const item of list){
const { id } =item;
map.set(id, {...item});
}
// 遍历Map， 如果有父级，就添加到父级的children中去
for(const [id, item] of map){
const { parentId } = item;
const parent = map.get(parentId);
if(parent){
parent.children = parent.children || [];
const children = parent.children;
const findIndex = children.findIndex((child) => id === child.id );
// 是否存在，避免重复添加
if(findIndex === -1){
children.push(item);
}
}
}
// 取parentId为0的项
return Array.from(map.values()).filter(item => item.parentId === 0);
}
function convert(list) { return list.reduce((result, item) => { item.child = [] result[item.id] = item; result[item.parentId].child.push(item) return result }, {'0': {child: []}})[0].child }
這個寫法依賴result裡面要先有特定item，
所以有機會result[item.parentId]會是undefined，例如input是：
[
{ id: 7, name: '部门G', parentId: 2 },
{ 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: 8, name: '部门H', parentId: 4 }
]
O(n) 加上一個children map的空間：
var solution = list => {
const firstDeps = [];
const depChilds = {};
list.forEach(dep => {
if (dep.parentId === 0) {
firstDeps.push(dep);
} else {
depChilds[dep.parentId] = depChilds[dep.parentId] || [];
depChilds[dep.parentId].push(dep);
}
depChilds[dep.id] = depChilds[dep.id] || [];
dep.children = depChilds[dep.id];
});
return firstDeps;
};
reduce实现
function convert(list) {
return list.reduce((pre, cur, index, arr) => {
if (cur.parentId === 0) pre.push(cur)
else {
const parent = arr.find(item => item.id === cur.parentId)
if (parent) {
parent.children = parent.children || []
parent.children.push(cur)
}
}
return pre
}, [])
}
递归实现
function convert(list, result = []) {
list.forEach(item => {
if (item.parentId === 0) result.push(item)
else {
const parent = list.find(r => r.id === item.parentId)
if (parent) {
parent.children = parent.children || []
parent.children.push(item)
convert(parent.children, result)
}
}
})
return result
}
迭代实现
function convert(list) {
const result = []
let parent = result
list.forEach(item => {
if (item.parentId === 0) parent.push(item)
else {
const finded = list.find(r => r.id === item.parentId)
if (finded) {
parent = finded
parent.children = parent.children || []
parent.children.push(item)
}
}
})
return result
}
全都是O(n^2)
function convert(list) {
const res = [];
const map = {};
list.forEach((item) => {
map[item.id] = item;
});
for (const item of list) {
const parent = map[item.parentId];
if (item.parentId === 0) {
res.push(item);
} else if (parent) {
(parent.children || (parent.children = [])).push(item);
}
}
return res;
}
function convert(list = []) {
//最后返回的树
let result = [];
//造出最先的顶级树
list.forEach(it => {
if (!list.map(it => it.id).includes(it.parentId)) {
result.push(it);
}
})
buildTree(result, list);
return result;
}
function buildTree(fatherTree, list) {
list.forEach(item => {
fatherTree.forEach(it => {
//给父树添加节点
if (it.id == item.parentId) {
if (!it.hasOwnProperty('children')) {
it.children = [];
}
it.children.push(item)
}
})
})
fatherTree.forEach(item => {
if (item.hasOwnProperty('children') && Array.isArray(item.children)) {
//父树有子节点的让子节点都递归
buildTree(item.children, list)
}
})
}
function convert(list) {
const map = {};
const res = [];
list.forEach((item) => {
const obj = {
id: item.id,
name: item.name,
parentId: 0,
};
if (map[item.id]) { // 之前简单生成的数据没有name和parentId,此时添加上
map[item.id].name = item.name;
map[item.id].parentId = item.parentId;
} else {
map[item.id] = obj;
}
if (item.parentId === 0) {
res.push(map[item.id]);
} else {
if (map[item.parentId]) {
map[item.parentId].children = map[item.parentId].children
? map[item.parentId].children.concat(map[item.id])
: [map[item.id]];
} else {
// 如果此时对于的parentId部门在map中没有对于值，先简单生成
map[item.parentId] = {
id: item.parentId,
children: [map[item.id]],
};
}
}
});
return res;
}
O(n)时间复杂度，边遍历编生成map，可以处理顺序不对的情况
const list = [
{ id: 3, name: '部门C', parentId: 1 }, // 此时部门1还没有生成，
{ id: 1, name: '部门A', parentId: 0 },
{ id: 2, name: '部门B', parentId: 0 },
{ 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 },
];
function convert(arr) { let map = {}, list = [] arr.forEach(item => { map[item.id] = item }); for (let item of arr) { if (item.parentId === 0) { list.push(item) } else { if (map[item.parentId]) { const parent = map[item.parentId] parent.children = parent.children || [] parent.children.push(item) } }
}
return list;
}
function convert(data) {
const idMapping = data.reduce((acc, cur, index) => {
acc[cur.id] = index
return acc
}, {})
const arr = []
data.forEach(el => {
if (el.parentId === 0) {
arr.push(el)
return
}
const parentEl = data[idMapping[el.parentId]]
parentEl.children = [...(parentEl.children || []), el]
})
return arr
}
const listToTree = (tree) => {
const map = tree.reduce((map, crt) => (map[crt.id] = crt, crt.children = [], map), {})
return tree.filter(node => {
node.parentId && map[node.parentId].children.push(node)
return !node.parentId
})
}
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 },
{ id: 9, name: '部门I', parentId: 10 },
];
const result = convert(list);
function convert(list) {
list = list.sort((a, b) => a.parentId - b.parentId);
let i = list.length - 1;
while (i > 0) {
const item = list[i];
const parent = list.find(itm => itm.id === item.parentId);
if (parent) {
parent.children = parent.children || [];
parent.children.push(item);
list.splice(i, 1);
}
i--;
}
return list;
}
console.log(result);
一次遍历搞定
function convert(list) {
const root = {
children: []
};
const map = {
0: root
};
for (let item of list) {
const { id, name, parentId } = item;
const current = map[id] || (map[id] = {
children: []
})
current.id = id;
current.name = name;
const parent = map[parentId] || (map[parentId] = {
children: []
})
parent.children.push(current);
}
return root.children;
}
***@***.*** added you to their Edison Mail+ Family Plan
***@***.*** added you to their Edison Mail+ Family Plan
Welcome to the family! Access your new Edison Mail+ premium email features by connecting this email
account to the Edison Mail app. You will continue to have free access as long as ***@***.***
has an active Plus subscription.
Maximize your email security, block spam calls, and more!
Don't have the app?
const convert=(list)=>{
const map={};
const result=[];
for (let index = 0; index < list.length; index++) {
map[list[index].id]=list[index]
}
for (let index = 0; index < list.length; index++) {
const element = list[index];
if(element.parentId==0){
result.push(element)
}else{
if(element.parentId in map){
if(map[element.parentId].children){
map[element.parentId].children.push(element)
}else{
map[element.parentId].children=[element]
}
}
}
}
return result
}
/**
* record := {}
* i := 0
* while i < list.length
* if record[list[i].parentId] == null
* record[list[i].parentId] := [];
* end if
* record[list[i].parentId].push(list[i]);
* i += 1
* i := 0
* res := []
* while i < list.length
* treeNode := list[i]
* if treeNode.parentId === 0
* res.push(treeNode)
* end if
* children := record[treeNode.id] || []
* treeNode.children = children
* i += 1
* return res
*/
const solution = (list) => {
const record = list.reduce((res, node, idx) => {
if (!res[node.parentId]) res[node.parentId] = [];
res[node.parentId].push(list[idx]);
return res;
}, {});
let res = [];
list.forEach((ele) => {
const treeNode = ele;
if (treeNode.parentId === 0) res.push(treeNode);
treeNode.children = record[treeNode.id] || [];
});
return res;
};
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 }
];
solution(list);
const convert = list => {
for (let i = 0, length = list.length; i < length; i++) {
const el = list[i];
el.children = el.children || [];
let index = list.findIndex(v => v.id == el.parentId);
if (index !== -1) {
list[index].children.push(el);
}
}
return list.filter(v => v.parentId == 0);
};
这样有什么问题吗
