共计 1554 个字符，预计需要花费 4 分钟才能阅读完成。
偶然间，在技术群里聊到生成有限层级树的老话题，故此记录下，n 年前一次生成有限层级树的解决方案
业务场景
解决国家行政区域的树，省市区，最小颗粒到医院，后端回包平铺数据大小 1M 多，前端解决数据后再渲染，卡顿显著
后端返回的数据结构
[
{
"id": 1,
"name": "中华人民共和国",
"parentId": 0,
},
{
"id": 1001,
"name": "浙江省",
"parentId": 1,
},
{
"id": 2001,
"name": "杭州市",
"parentId": 1001,
},
{
"id": 3001,
"name": "西湖区",
"parentId": 2001,
},
{
"id": 4001,
"name": "杭州市第一人民医院",
"parentId": 3001,
},
// 其余略
]第一版：递归解决树
惯例解决形式
// 略，网上一抓一把第二版：非递归解决树
改进版解决形式
const buildTree = (itemArray, { id = 'id', parentId = 'parentId', children = 'children', topLevelId = '0'} = {}) => {return itemArray.filter((item) => {
// 挂载子级
item[children] = itemArray.filter((child) => String(item[id]) === String(child[parentId]));
// 返回顶层数据
return String(item[parentId]) === topLevelId;
});
};工夫复杂度：O(n^2)
第三版：非递归解决树
import {groupBy} from 'lodash';
const buildTree = (itemArray, { id = 'id', parentId = 'parentId', children = 'children', topLevelId = '0'} = {}) => {const parentObj = groupBy(itemArray, parentId)
return itemArray.filter((item) => {
// 挂载子级
item[children] = parentObj[item[id]];
// 返回顶层数据
return String(item[parentId]) === topLevelId;
});
};工夫复杂度：O(2n)
最终版：非递归解决树
const buildTree = (itemArray, { id = 'id', parentId = 'parentId', children = 'children', topLevelId = '0'} = {}) => {const parentMap = new Map(); // 长期存储所有父级
const topLevelResult = []; // 存储顶层后果
for(let item of itemArray) {if(!parentMap.has(item[id])) {item[children] = []} else {item[children] = parentMap.get(item[id])[children];
}
parentMap.set(item.id, item)
if(!parentMap.has(item[parentId])) {parentMap.set(item[parentId], {[children]: []});
}
parentMap.get(item[parentId])[children].push(item)
if (String(item[parentId]) === String(topLevelId)) {topLevelResult.push(item)
}
}
return topLevelResult;
}工夫复杂度：O(n)
下篇分享 不必递归有限层级树取交加
正文完