【前端手撕】数组转树

把平铺的数组结构转换为树结构。const arr [ { id: 01, name: 张大大, pid: , job: 项目经理 }, { id: 02, name: 小亮, pid: 01, job: 产品leader }, { id: 03, name: 小美, pid: 01, job: UIleader }, { id: 04, name: 老马, pid: 01, job: 技术leader }, { id: 05, name: 老王, pid: 01, job: 测试leader }, { id: 06, name: 老李, pid: 01, job: 运维leader }, { id: 07, name: 小丽, pid: 02, job: 产品经理 }, { id: 08, name: 大光, pid: 02, job: 产品经理 }, { id: 09, name: 小高, pid: 03, job: UI设计师 }, { id: 10, name: 小刘, pid: 04, job: 前端工程师 }, { id: 11, name: 小华, pid: 04, job: 后端工程师 }, { id: 12, name: 小李, pid: 04, job: 后端工程师 }, { id: 13, name: 小赵, pid: 05, job: 测试工程师 }, { id: 14, name: 小强, pid: 05, job: 测试工程师 }, { id: 15, name: 小涛, pid: 06, job: 运维工程师 }, ];转换为[ { id: 01, name: 张大大, pid: , job: 项目经理, children: [ { id: 02, name: 小亮, pid: 01, job: 产品leader, children: [ { id: 07, name: 小丽, pid: 02, job: 产品经理, children: [] }, { id: 08, name: 大光, pid: 02, job: 产品经理, children: [] } ] }, // ... 其他子节点 ] } ]暴力递归function toTree(list, parId ) { let len list.length function loop(parId) { let res [] // 存当前层的所有子节点 // 递归遍历整个数组找到当前层所有子节点注意每次都是遍历全部 for (let i 0; i len; i) { if (list[i].pid parId) { // 如果当前项的父id是parId说明是当前层的子节点 // 递归调用loop函数找到当前项的所有子节点 list[i].children loop(list[i].id) // 把当前节点带着它的children放入结果 res.push(list[i]) } } return res } return loop(parId) }因为每次递归都是遍历整个数组所以时间复杂度是O(n²)数据量大的时候会很慢。遍历数组其实是为了找到父节点对应的子节点并进行组装。因此可以先用map来做一次映射方便父子节点的快速定位和组装。优化为用哈希来解哈希解法function toTreeHash(list) { const res [] const map {} // 先把所有项都放到哈希表中浅拷贝不污染原数组 arr.forEach(item map[item.id] {...item, children:[]}) // 遍历数组根据父id找到子节点把子节点放到父节点的children数组中 for (let item of list) { let node map[item.id] if (item.pid) { // 避免父节点不存在的情况导致报错 if (!map[item.pid]) continue // 把当前项放到父节点的children数组中 map[item.pid].children.push(node) } else { // 没有父id说明是根节点 res.push(node) } } return res }因为只遍历两次数组时间复杂度为O(n)。