偶然间，在技术群里聊到生成有限层级树的老话题，故此记录下，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)