不用递归生成无限层级的树 javascript前端

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