面试常问：如何将扁平列表转换为树形结构？深入剖析两种优雅实现-北京尧图网络

后台管理系统中地址三级联动、多级菜单、组织架构树……这些常见功能都离不开一个核心操作——列表转树。今天我们就来彻底搞懂这个经典算法并对比两种优雅的 JavaScript 实现。一、为什么需要“列表转树”在关系型数据库如 MySQL中我们通常会用一张表存储具有层级关系的数据每条记录通过parentId指向父级。例如idnameparentId1一级菜单A02一级菜单B03一级菜单A-114一级菜单A-1-135一级菜单B-12当我们执行SELECT * FROM menu时得到的就是一个扁平列表一维数组。但前端渲染树形组件如 el-tree、z-tree或级联选择器时需要的是嵌套的树形结构[ { id: 1, name: 一级菜单A, children: [ { id: 3, name: 一级菜单A-1, children: [ { id: 4, name: 一级菜单A-1-1, children: [] } ] } ] }, { id: 2, name: 一级菜单B, children: [ { id: 5, name: 一级菜单B-1, children: [] } ] } ]所以列表转树是前后端协作中的基础技能也是面试中的高频手写题。二、原始数据我们沿用上面的菜单数据const flatList [ { id: 1, name: 一级菜单A, parentId: 0 }, { id: 2, name: 一级菜单B, parentId: 0 }, { id: 3, name: 一级菜单A-1, parentId: 1 }, { id: 4, name: 一级菜单A-1-1, parentId: 3 }, { id: 5, name: 一级菜单B-1, parentId: 2 }, ];核心逻辑每个节点通过parentId指向父节点parentId: 0表示根节点顶级。三、方法一利用Map建立索引经典易读思路第一次遍历将所有节点存入Map以id为键同时为每个节点初始化children空数组不影响原对象。第二次遍历取出当前节点根据其parentId找到父节点。若父节点存在将当前节点加入父节点的children中若父节点不存在即parentId为 0 或找不到说明当前节点是根节点直接放入tree数组。代码实现function listToTree(list) { const map new Map(); const tree []; // 第一步构建 id - node 映射并为每个节点准备 children list.forEach((item) { map.set(item.id, { ...item, // 展开原属性 children: [] // 新增子节点容器 }); }); // 第二步组装父子关系 list.forEach((item) { const current map.get(item.id); // 当前节点含 children const parent map.get(item.parentId); // 父节点含 children if (parent) { parent.children.push(current); // 挂到父节点下 } else { tree.push(current); // 没有父节点 → 根节点 } }); return tree; }逐步解析发生了什么map的妙用以id为键将每个节点平铺存储。注意我们使用了{ ...item, children: [] }这样新对象不会影响原flatList中的对象浅拷贝一层。为什么先存再组装因为flatList是乱序的比如子节点可能出现在父节点之前如果边遍历边挂载可能父节点尚未创建。但这里我们预先全部存入map所以无论如何都能找到父节点。根节点判断parentId 0时map.get(0)返回undefined因此该节点被直接推入tree数组。测试console.log(JSON.stringify(listToTree(flatList), null, 2));输出结果即为上面期望的树形结构。四、方法二一招reduce搞定函数式风格有些开发者偏爱reduce因为它能将遍历和累积过程浓缩在一个表达式里。我们可以用reduce同时完成构建映射和组装树。代码实现function listToTree(list) { // 用 reduce 构建 id - node 映射 const nodeMap list.reduce((map, item) { map[item.id] { ...item, children: [] }; return map; }, {}); // 初始化为空对象 // 再用 reduce 组装树 return list.reduce((tree, item) { const cur nodeMap[item.id]; const parent nodeMap[item.parentId]; if (parent) { parent.children.push(cur); } else { tree.push(cur); } return tree; }, []); // 初始化为空数组 }解析reduce的每一步reduce 记忆口诀通用语法arr.reduce((累加器, 当前元素, 当前索引, 原数组) { // 必须 return 累加器作为下一次迭代的“累加器” }, 初始值);两个关键点初始值决定了累加器的类型写{}最终得到对象写[]最终得到数组写0最终得到数字。必须return如果不return下一次累加器就会变成undefined导致程序报错。reduce是数组的归并方法arr.reduce(callback, initialValue)每次迭代将上次的累积结果accumulator与当前元素一起传入回调。第一步reduce累积器map初始为{}。每次迭代把item.id作为 key值为{ ...item, children: [] }。最后返回一个完整的映射对象nodeMap类似{ 1: {...}, 2: {...}, ... }。第二步reduce累积器tree初始为[]。每次迭代取出当前节点cur和父节点parent。如果父节点存在parent.children.push(cur)否则tree.push(cur)。最后返回tree即根节点数组。与 Map 版本的对比数据结构Map比普通对象更适合频繁查找因为Map的键可以是任意类型且查找效率稳定。不过这里id是数字对象也能胜任。代码风格reduce更“函数式”但嵌套两层reduce可读性稍逊于两次forEach。实际开发中两者都常见看团队偏好。性能两者都是 O(n) 时间复杂度只遍历两次性能优秀。五、扩展处理边界情况实际业务中可能会遇到以下问题我们可以优化数据顺序混乱我们的方法已经通过提前构建映射解决了父节点不必出现在子节点之前。循环引用如果数据错误出现parentId形成环如 A.parentId B, B.parentId A递归会导致死循环。但我们的方法只构建父子关系不会无限递归因为只遍历一次不会追踪子子孙孙。根节点标识有的系统用null或0表示根节点parentId不存在则视为根。我们可以将parentId做类型统一例如if (item.parentId null || item.parentId 0)。原地修改 vs 拷贝我们使用{ ...item }复制了对象避免污染原始数据。如果不需要保留原数据也可以直接修改原对象但为了安全建议复制。六、总结应用场景后台管理系统的菜单树、组织架构、评论楼中楼、地区级联等。核心思想利用id和parentId建立映射通过两次线性遍历完成组装。两种实现MapforEach清晰直观reduce更简洁但需要理解归并过程。面试亮点手写时注意先映射再组装避免顺序依赖提到空间换时间用 Map 或对象存储索引考虑递归转迭代减少栈风险但这里无需递归。掌握了这个算法你再也不用写复杂的递归去遍历了而且效率更高。下次面试官问起不妨自信地写出这两种实现并解释其背后的原理。

面试常问：如何将扁平列表转换为树形结构？深入剖析两种优雅实现

相关推荐

DeepInsightTheorem：基于技巧识别的LLM数学推理增强框架

Go数学计算避坑指南：精度、溢出与类型安全实战

Ubuntu 14.04 Droplet自动扩缩容实战：Shell级轻量方案

更多资讯

怎么考水电工证的，外省证能转过来吗？报名流程全解析

新疆电工证在哪里查询多少钱？学历不高也能报名的实操指南

电工证掉了只要有编号怎么补救？官方报名入口在这儿

电工证多久能查考在外省的证千万别踩坑

电工证的其他用途你知道还能干啥吗？通过率揭秘

弱电有电工证吗保姆级教程：工地太忙根本没时间复习考试怎么办

今日更新

特种工指挥考试题库怎么刷才不会白交培训费？官方报名入口在这！

电工证考试多少分合格在哪考别再交冤枉钱了

福清应急管理局电工证真实经历：工地太忙根本没时间复习考试怎么办

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？