手写数组扁平化

一句话概括

数组扁平化就是把 [1, [2, [3, 4]]] 变成 [1, 2, 3, 4]。面试不考你知不知道 arr.flat()，考的是递归、栈、Generator 三种思路的取舍——以及什么时候递归会爆。

核心知识点

1. 递归实现 — 最直白

function flatten(arr) {
  const result = [];
  for (const item of arr) {
    Array.isArray(item) ? result.push(...flatten(item)) : result.push(item);
  }
  return result;
}

flatten([1, [2, [3, [4]]]]); // [1, 2, 3, 4]

优点够直观，缺点嵌套超过 ~10000 层会爆栈。函数式写法本质一样：

const flatten = arr =>
  arr.reduce((acc, cur) => acc.concat(Array.isArray(cur) ? flatten(cur) : cur), []);

2. 栈实现 — 非递归不爆栈

function flatten(arr) {
  const stack = [...arr];
  const result = [];
  while (stack.length) {
    const next = stack.pop();
    Array.isArray(next) ? stack.push(...next) : result.push(next);
  }
  return result.reverse(); // 栈是 LIFO，结果需要反转
}

为什么需要 reverse()？ 栈是后进先出：[1, [2, 3]] → pop 出 [2, 3] → push 回 2 和 3 → 栈变成 [1, 2, 3] → 再 pop 是 3。最终 result 是 [3, 2, 1]，必须反转。

想不要 reverse？用 shift + push 把栈当队列用——但 shift 是 O(n)，整体变 O(n²)。

3. Generator — 惰性求值

function* flatten(arr) {
  for (const item of arr) {
    Array.isArray(item) ? yield* flatten(item) : yield item;
  }
}

// 逐个消费，不一次性展开
for (const val of flatten(hugeArray)) {
  process(val); // 内存友好
}

// 也可以一次性收集
[...flatten([1, [2, [3]]])]; // [1, 2, 3]

yield* 不是递归调用！ Generator 的 yield* 是把子 Generator 的产出值逐个转发，不会建立调用栈。这是惰性求值的精髓。

4. 指定深度扁平化

function flatten(arr, depth = Infinity) {
  return depth > 0
    ? arr.reduce(
        (acc, cur) =>
          acc.concat(Array.isArray(cur) ? flatten(cur, depth - 1) : cur),
        []
      )
    : arr.slice();
}

const data = [1, [2, [3, [4]]]];
flatten(data, 1); // [1, 2, [3, [4]]]
flatten(data, 2); // [1, 2, 3, [4]]

5. 三种方案对比

	递归	栈	Generator
代码量	最少	中等	中等
爆栈风险	✅ 有	❌ 无	❌ 无
惰性消费	❌	❌	✅
深层性能	O(n) 但可能爆	O(n) 稳定	O(n) 稳定

其实你每天都在用

• API 返回的树形数据展平：接口返回 [{ id:1, children:[...] }, ...]，扁平后丢给表格组件渲染
• 文件目录 → 路径列表：树形文件夹结构展平后生成面包屑导航
• 路由配置展平：Vue Router / React Router 的嵌套路由，展平后批量注册
• 批量数据处理：多个数据源各自返回不同层级的数据，先 flat 再统一 transform
• DOM 深遍历：element.children 是嵌套的，展平后全量操作

常见误解

• ❌ 误区：「递归是万能方案」 生产环境中嵌套层级不确定时，递归可能爆栈。DeepL 的翻译数据、AST 遍历这些真实场景递归深度可能上万。大数据量或深层嵌套用栈或 Generator。

• ❌ 误区：「arr.flat(Infinity) 就够了，不需要手写」 语法上够了，面试考的是原理。而且 flat 是同步一次性展开，不支持惰性消费——如果你有十万条数据要边展平边处理，Generator 才是正解。

• ❌ 误区：「栈实现里的 reverse() 浪费性能」 reverse() 是 O(n)，和 flatten 本身的 O(n) 同量级，代价可接受。用 shift() 避免 reverse 反而会把整体变成 O(n²)。

• ❌ 误区：「Array.isArray 够用了，不用考虑类数组」 实际场景中 arguments、NodeList、FileList 都是类数组但 Array.isArray 返回 false。如果要覆盖这些，先 Array.from() 转换。

一句话总结

面试时三步走：先写递归表达思路，再上栈实现表现深度（同时解释为什么要 reverse），最后提一嘴 Generator 的惰性求值场景——三件套打完，面试官直接问下一题。