【前端手撕】数组转树

把平铺的数组结构转换为树结构。

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)。