登录JavaScript 列表转树（List to Tree）详解：前端面试中如何从递归 O(n²) 优化到一次遍历 O(n)
前言：Offer 是怎么没的？
在前端面试的江湖里，「列表转树（List to Tree）」 是一道妥妥的高频题。
很多同学一看到这道题，内心 OS 都是：
😎「简单啊，递归！」
代码写完，自信抬头。
面试官却慢悠悠地问了一句：
🤨「如果是 10 万条数据 呢？
👉 时间复杂度多少？
👉 会不会栈溢出？」
空气突然安静。
今天这篇文章，我们就把这道题彻底拆开：
从「能写」到「写得对」，再到「写得漂亮」。
一、为什么面试官总盯着这棵“树”？
因为在真实业务中，后端给你的几乎永远是扁平数据。
例如：
const list = [
{ id: 1, parentId: 0, name: '北京市' },
{ id: 2, parentId: 1, name: '顺义区' },
{ id: 3, parentId: 1, name: '朝阳区' },
{ id: 4, parentId: 2, name: '后沙峪' },
{ id: 121, parentId: 0, name: '江西省' },
{ id: 155, parentId: 121, name: '抚州市' }
];
而前端组件（Menu、Tree、Cascader）要的却是👇
省
└─ 市
└─ 区
🎯 面试官的真实考点
-
数据结构理解：是否真正理解
parentId - 递归意识 & 代价：不只会写，还要知道坑在哪
-
性能优化能力：能否从
O(n²)优化到O(n) - JS 引用理解：是否理解对象在内存中的表现
二、第一重境界：递归法（能写，但不稳）
1️⃣ 最基础的递归写法
function list2tree(list, parentId = 0) {
return list
.filter(item => item.parentId === parentId)
.map(item => ({
...item,
children: list2tree(list, item.id)
}));
}
逻辑非常直观：
- 找当前
parentId的所有子节点 - 对每个子节点继续递归
- 没有子节点时自然退出
三、进阶：ES6 优雅写法（看起来很高级）
如果你在面试中写出下面这段代码👇
面试官大概率会先点头。
const list2tree = (list, parentId = 0) =>
list
.filter(item => item.parentId === parentId)
.map(item => ({
...item, // 解构赋值，保持原对象纯净
children: list2tree(list, item.id)
}));
这一版代码：
- ✅ 箭头函数
- ✅
filter + map链式调用 - ✅ 解构赋值，不污染原数据
- ✅ 可读性很好，看起来很“ES6”
👉 很多同学到这一步就觉得稳了。
🤔 面试官的经典追问
「这个方案，有什么问题？」
🎯 标准回答（一定要说出来）
「这个方案的本质是 嵌套循环。
每一层递归，都会遍历一次完整的list。👉 时间复杂度是
O(n²)
👉 如果层级过深，还可能导致 栈溢出（Stack Overflow） 。」
📌 一句话总结：
ES6 写法只是“看起来优雅”，
性能问题不会因为代码好看就自动消失。
四、第二重境界：Map 优化（面试及格线）
既然慢，是因为反复遍历找父节点，
那就用 Map 建立索引。
👉 典型的：空间换时间
核心思路
- 第一遍：把所有节点放进
Map - 第二遍：通过
parentId直接挂载 - 利用 JS 对象引用，自动同步树结构
代码实现
function listToTreeWithMap(list) {
const map = new Map();
const tree = [];
// 初始化
for (const item of list) {
map.set(item.id, { ...item, children: [] });
}
// 构建树
for (const item of list) {
const node = map.get(item.id);
if (item.parentId === 0) {
tree.push(node);
} else {
const parent = map.get(item.parentId);
parent && parent.children.push(node);
}
}
return tree;
}
⏱ 复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
📌 到这一步，已经可以应付大多数面试了。
五、终极奥义：一次遍历 + 引用魔法（Top Tier）
面试官：
「能不能只遍历一次？」
答案是：能，而且这才是天花板解法。
核心精髓：占位 + 引用同步
- 子节点可能先于父节点出现
- 先在 Map 里给父节点 占位
- 后续再补全数据
- 引用地址始终不变，树会“自己长好”
代码实现（一次遍历）
function listToTreePerfect(list) {
const map = new Map();
const tree = [];
for (const item of list) {
const { id, parentId } = item;
if (!map.has(id)) {
map.set(id, { children: [] });
}
const node = map.get(id);
Object.assign(node, item);
if (parentId === 0) {
tree.push(node);
} else {
if (!map.has(parentId)) {
map.set(parentId, { children: [] });
}
map.get(parentId).children.push(node);
}
}
return tree;
}
🏆 为什么这是王者解法？
- ✅ 一次遍历，
O(n) - ✅ 支持乱序数据
- ✅ 深度理解 JS 引用机制
- ✅ 面试官一眼就懂你是“真会”
六、真实开发中的应用场景
- 🔹 权限 / 菜单树（Ant Design / Element）
- 🔹 省市区 / Cascader
- 🔹 文件目录结构（云盘、编辑器）
七、面试总结 & 避坑指南
| 方案 | 时间复杂度 | 评价 |
|---|---|---|
| 递归 | O(n²) |
能写，但危险 |
| Map 两次遍历 | O(n) |
面试合格 |
| 一次遍历 | O(n) |
面试加分 |
面试加分表达
- 主动提 空间换时间
- 点出 JS 对象是引用类型
- 询问
parentId是否可能为null - 说明是否会修改原数据（必要时深拷贝）
结语
算法不是为了为难人，
而是为了在复杂业务中，
选出那条最稳、最优雅的路。
如果这篇文章对你有帮助👇
👍 点个赞
💬 评论区聊聊你在项目里遇到过的奇葩数据结构
