1、递归方式
const list = [ { id: '001', name: '节点1' }, { id: '0011', parentId: '001', name: '节点1-1' }, { id: '00111', parentId: '0011', name: '节点1-1-1' }, { id: '002', name: '节点2' }, ] /** * 数组转树形结构 * @param {*} list 数组 * @param {*} parentId 父级id * @param {*} param2 可配置参数 */ const transformArrToTree =(list,parentId,{idName="id",parentIdName="parentId",childrenName="children"}={})=>{ if(!Array.isArray(list)){ new Error('only Array') return list } return list.reduce((prev,next)=>{ if(next[parentIdName]===parentId){ const children= transformArrToTree(list,next[idName]) if(children?.length){ next[childrenName]=children } return[...prev,next] } return prev; },[]) } console.log('ss',transformArrToTree(list))View Code
2、非递归方式
const transformArrToTree =(list,rootId,{idName="id",parentIdName="parentId",childrenName="children"}={})=>{ if(!Array.isArray(list)){ new Error('only Array') return list } const objMap={} // 暂存数组以id为key映射关系 const result=[] for(const item of list) { const id=item[idName] const parentId=item[parentIdName] // 该元素有可能放入map中(找不到该项的parent时会先放入map) objMap[id]=!objMap[id] ? item:{...item,...objMap[id]} //找到对应映射关系 const treeItem=objMap[id] if(parentId===rootId){ result.push(treeItem) }else{ if(!objMap[parentId]){ objMap[parentId]={} } if(!objMap[parentId][childrenName]){ objMap[parentId][childrenName]=[] } objMap[parentId][childrenName].push(treeItem) } } return result } console.log('数组转树形结构=>',transformArrToTree(list))View Code
- 递归方式:每次递归寻找当前节点的子节点时都需要重新遍历一遍数组,时间复杂度为 O(nlogn)
- 非递归方式:从根节点往下寻找子节点,通过 Map 保存每个节点及其子节点的信息,子节点保存的是 Map 上的引用,每个节点的子节点都可以在 Map 中通过 id 找到,时间复杂度为 O(n)
- 当数据越来越大时,递归算法的耗时将远远大于非递归算法