登录从零到一：彻底搞定面试高频算法——“列表转树”与“爬楼梯”全解析
在前端面试中，算法往往是决定能否拿高薪的关键。很多同学一听到“算法”就头大，觉得那是天才玩的游戏。其实，大多数面试算法题考察的不是你的数学造诣，而是你对递归（Recursion）和逻辑处理的理解。
今天，我们就通过两个非常经典的面试真题—— “列表转树（List to Tree）”和“爬楼梯（Climbing Stairs）” ，带你从小白视角拆解算法的奥秘。
第一部分：列表转树 —— 业务中的“常青树”
1. 为什么要学这个？
在实际开发中，后端返回给我们的数据往往是“扁平化”的。比如一个省市区选择器，或者一个后台管理系统的左侧菜单导航。为了存储方便，数据库通常会存储为如下结构：
| id | parentId | name |
|---|---|---|
| 1 | 0 | 中国 |
| 2 | 1 | 北京 |
| 3 | 1 | 上海 |
| 4 | 2 | 东城区 |
但前端 UI 组件（如 Element UI 的 Tree 组件）需要的是一个嵌套的树形对象。如何把上面的表格数据转换成包含 children 的树？这就是面试官考察你的数据结构处理能力。
2. 解法一：暴力递归（最符合人类直觉）
核心逻辑：
- 遍历列表，找到根节点（
parentId === 0）。 - 对于每一个节点，再去列表里找谁的
parentId等于我的id。 - 递归下去，直到找不到子节点。
// 代码参考
function list2tree(list, parentId = 0) {
const result = [];
list.forEach(item => {
if (item.parentId === parentId) {
// 这里的递归就像是在问：谁是我的孩子？
const children = list2tree(list, item.id);
if (children.length) {
item.children = children;
}
result.push(item);
}
});
return result;
}
小白避坑指南：
这种方法的复杂度是 。如果列表有 1000 条数据，最坏情况下要跑 100 万次循环。面试官此时会问：“有没有更优的方法？”
3. 解法二：优雅的 ES6 函数式写法
如果你想让代码看起来更“高级”，可以利用 filter 和 map：
function list2tree(list, parentId = 0) {
return list
.filter(item => item.parentId === parentId) // 过滤出当前的子节点
.map(item => ({
...item, // 展开原有属性
children: list2tree(list, item.id) // 递归寻找后代
}));
}
4. 解法三：空间换时间（面试官最爱）
为了把时间复杂度降到 ，我们可以利用 Map 对象。Map 的查询速度极快，像是一个“瞬移器”。
思路：
- 先遍历一遍列表，把所有节点存入 Map 中，以
id为 Key。 - 再遍历一遍，根据
parentId直接从 Map 里把父节点“揪”出来，把当前节点塞进父节点的children里。
// 代码参考
function listToTree(list) {
const nodeMap = new Map();
const tree = [];
// 第一遍：建立映射表
list.forEach(item => {
nodeMap.set(item.id, { ...item, children: [] });
});
// 第二遍：建立父子关系
list.forEach(item => {
const node = nodeMap.get(item.id);
if (item.parentId === 0) {
tree.push(node); // 根节点入队
} else {
// 直接通过 parentId 找到父亲，把儿子塞进去
nodeMap.get(item.parentId)?.children.push(node);
}
});
return tree;
}
优点： 只遍历了两遍列表。无论数据有多少，速度依然飞快。
第二部分：爬楼梯 —— 掌握算法的“分水岭”
如果说“列表转树”考察的是业务能力，那“爬楼梯”考察的就是编程思维。
题目描述： 假设你正在爬楼梯。需要 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
1. 自顶向下：递归的艺术
我们站在第 阶往回看：
- 要到达第 10 阶，你只能从第 9 阶跨 1 步上来，或者从第 8 阶跨 2 步上来。
- 所以：。
这就是著名的斐波那契数列公式。
// 基础版
function climbStairs(n) {
if (n === 1) return 1;
if (n === 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
致命缺陷： 这个代码会跑死电脑。算 时要算 和 ；算 时又要算一遍 。大量的重复计算导致“爆栈”。
2. 优化：带备忘录的递归（记忆化）
我们可以准备一个“笔记本”（memo），算过的值就记下来，下次直接拿。
const memo = {};
function climbStairs(n) {
if (n === 1) return 1;
if (n === 2) return 2;
if (memo[n]) return memo[n]; // 翻翻笔记，有就直接给
memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
return memo[n];
}
3. 自底向上：动态规划（DP）
动态规划（Dynamic Programming）听起来很高大上，其实就是倒过来想。
我们不从 往回找，而是从 开始往后推：
function climbStairs(n) {
if (n <= 2) return n;
const dp = new Array(n + 1);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 每一个结果都是前两个的和
}
return dp[n];
}
4. 极致优化：滚动变量
既然 只依赖前两个数，那我们连数组都不需要了，只需要三个变量在手里“滚”起来。
function climbStairs(n) {
if(n <= 2) return n;
let prePrev = 1; // f(n-2)
let prev = 2; // f(n-1)
let current;
for(let i = 3; i <= n; i++){
current = prev + prePrev;
prePrev = prev;
prev = current;
}
return current;
}
这时的空间复杂度降到了 ，几乎不占用额外内存。
总结：小白如何精进算法？
通过这两道题，你应该能发现算法学习的规律：
- 先画图，后写码： 不管是树状结构还是楼梯台阶，画出逻辑图比直接写代码重要得多。
- 寻找重复子问题： 递归和 DP 的核心都在于把大问题拆解成一样的小问题。
- 从暴力到优化： 别指望一步写出最优解。先用最笨的方法写出来，再去思考如何减少重复计算。
