手写数组扁平化深度解析

一句话概括

把 [1, [2, [3, [4]]]] 变成 [1, 2, 3, 4]——面试官不关心你知道 arr.flat(Infinity)，考的是递归爆栈风险、栈实现为什么必须 reverse()、Generator 惰性求值怎么省内存。三道牌打完，这道题毕业。

核心知识点

1. 递归 — 3 行搞定，但有硬伤

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

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

优点： 简洁。致命伤： 嵌套深度 ≈ 递归深度，V8 调用栈约一万层，超过直接 RangeError: Maximum call stack size exceeded。AST 遍历、深度嵌套的爬虫数据都踩过这个坑。

2. 栈实现 — 不爆栈，但有个必须解释的细节

function flatten(arr) {
  const stack = [...arr];
  const result = [];
  while (stack.length) {
    const item = stack.pop();
    if (Array.isArray(item)) {
      stack.push(...item);          // 展开子数组
    } else {
      result.push(item);
    }
  }
  return result.reverse();          // ⚠️ 面试官等的就是这句——为什么？
}

// 推演 [1, [2, [3]]]：
// stack: [1, [2,[3]]] → pop [2,[3]], push 2,[3] → [1, 2, [3]]
// pop [3], push 3                       → [1, 2, 3]
// pop 3,2,1 → result: [3, 2, 1]        → reverse → [1, 2, 3] ✅

为什么 reverse() 省不了： pop() 取最后一个 + push() 加到末尾 → 子数组元素展开后顺序反了。用 shift()/unshift() 代替确实不需要 reverse，但 shift() 会触发所有元素前移一位（O(n)），套在 while 循环里退化成 O(n²)——这才是真正不能忍的。

3. Generator — 惰性求值，百万数据不爆内存

function* flatten(arr) {
  for (const item of arr) {
    if (Array.isArray(item)) {
      yield* flatten(item);   // yield* 委托子生成器
    } else {
      yield item;
    }
  }
}

// 惰性消费：内存里同时只有当前元素
for (const val of flatten(hugeArray)) {
  process(val);               // 百万条数据也不会同时加载到内存
}

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

yield* 的核心价值： 它把子 Generator 的产出逐个转发给外层——配合迭代器的暂停/恢复机制实现按需产出，这就是 Generator 内存友好、适合流式处理的底层原理。

4. 指定深度（可选加分项）

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

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

方案对比

	递归	栈	Generator
爆栈风险	✅ 有（~万层）	❌	❌
惰性求值	❌	❌	✅
内存占用	高（全量）	高（全量）	低（按需）
可指定深度	容易	需额外跟踪	容易

其实你每天都在用

• 树形数据展平渲染：后端返回 [{id:1, children:[{id:2}]}] 的菜单/组织架构，flatten 后直接丢进 v-for 或虚拟滚动
• Vue Router 动态注册：权限接口返回嵌套路由，flatten 后 router.addRoute() 批量注册
• 文件树 → 面包屑：嵌套文件夹展平成路径列表，生成导航面包屑
• 多 API 数据合流：三个接口各自返回不同嵌套层级的数组，先 flat 再统一 map/filter
• DOM 深度遍历：element.children 深层嵌套，展平后统一绑定事件或查找节点

常见误解（FAQ）

• ❌ 误区：「递归最简洁，是最好的方案」 代码最短不等于最好。生产环境嵌套深度不可控（AST、爬虫数据、深度 JSON）时递归可能爆栈。大数据量用栈，惰性消费用 Generator——场景决定方案，不是行数决定方案。

• ❌ 误区：「arr.flat(Infinity) 一行搞定，手写没意义」 面试考的是原理理解。而且 flat() 是同步一次性全量展开——如果你有十万条数据要边展平边处理（流式场景），Generator 才是正解，flat() 做不到。

• ❌ 误区：「reverse() 多此一举，用 shift/unshift 就完了」 reverse() 是 O(n)，flatten 本身也是 O(n)，同量级。真正要命的是用 shift() 代替 pop()——每次 shift 导致所有剩余元素前移一位，O(n) 套在 while 循环里就是 O(n²)。

• ❌ 误区：「Array.isArray 判断数组就够了」 arguments、NodeList、FileList 等类数组对象 Array.isArray 返回 false。需要兼容时用 Array.from() 先转换，或用 Symbol.iterator 检测可迭代性。

一句话总结

面试三件套：递归说清思路 → 栈实现讲透 reverse() 原因 → Generator 提一嘴惰性求值。这三张牌打完，面试官直接下一题。