深搜与广搜在 TypeScript 类型递归中的应用

type

status

date

slug

summary

问题描述

FlattenDepth 的任务是将嵌套数组按指定深度进行扁平化：

看似简单的需求，但在实现时却有着巧妙的递归策略选择。这道题的核心挑战在于如何高效地控制扁平化的深度，不同的实现思路会产生截然不同的递归行为。

方案一：广度优先搜索（BFS）

实现思路

我最初的实现采用了广度优先的策略：先实现一次扁平化的逻辑，然后递归调用指定次数。这种方法的核心思想是"分而治之"，将复杂的多层扁平化分解为多次单层扁平化。

执行过程详细分析

让我们通过一个具体的例子来深入理解这种广度优先的执行过程。以 FlattenDepth<[1, [2, [3]]], 2> 为例：

第一次递归调用

第二次递归调用

第三次递归调用

广搜特征分析

这种方式完美体现了广度优先搜索的特征：

层级处理：每次 FlattenOnce 调用都会处理当前数组的所有元素，将所有一级嵌套都展开

统一深度：每次递归都让所有元素的嵌套深度统一减少 1

计数控制：通过数组 A 的长度来精确控制递归次数

问题

当我运行测试用例时，发现最后一个测试用例无法通过：

这个方案的致命问题在于递归深度与指定参数直接相关：

线性递归特征：无论数组的实际嵌套深度如何，都必须递归调用 FlattenDepth 恰好 N 次

资源消耗：每次递归都需要：

调用 FlattenOnce 遍历整个数组

创建新的累积数组 [...A, '']

维护递归调用栈

递归深度限制：TypeScript 的递归深度限制通常在 100-1000 层之间，19260817 次递归远超这个限制

用数学表达式来说明：

时间复杂度：O(N × M)，其中 N 是指定深度，M 是数组长度

空间复杂度：O(N)，需要维护 N 层递归栈

递归调用次数：恰好 N 次，与实际数据结构无关

所以我们需要转换思路，采用深搜。

方案二：深度优先搜索（DFS）

实现思路

深度优先的策略采用了完全不同的方法：按需递归，在遇到嵌套数组时立即深入处理，而不是等待当前层级处理完毕。这种方法的核心理念是"就地处理"，直接在原始结构上进行深度控制。

执行过程详细分析

让我们用同样的例子 FlattenDepth<[1, [2, [3]]], 2> 来理解深度优先的执行过程：

递归树结构分析

分步执行过程

第一层递归：

第二层递归：

第三层递归：

第四层递归：

第五层递归：

深搜特征分析

这种方式体现了深度优先搜索的核心特征：

就地决策：遇到数组立即决定是否深入，不需要等待同级元素处理完毕

路径记录：用 U 数组记录当前的递归路径深度

早期剪枝：一旦达到指定深度就停止深入，直接返回原结构

分治合并：将问题分解为"处理当前元素"和"处理剩余元素"两个子问题

优势分析

这种方式的关键优势在于：

1. 自适应递归深度

2. 早期终止机制

3. 空间效率优化

对于测试用例 FlattenDepth<[1, [2, [3, [4, [5]]]]], 19260817>：

实际嵌套深度：只有 4 层 [[[[[5]]]]]

递归行为：在第 4 层就会完成所有必要的扁平化

关键洞察：指定深度 19260817 虽然很大，但实际递归深度由数据结构决定

性能优势：总递归调用次数约为 O(数组长度 × 实际深度)，而非 O(指定深度)

深搜与广搜的本质差异

在算法中的表现

特性	广度优先搜索 (BFS)	深度优先搜索 (DFS)
空间复杂度	O(w) - 最大宽度	O(h) - 最大深度
时间复杂度	O(V + E)	O(V + E)
内存使用	需要存储整层节点	只需存储路径上节点
最优解	保证最短路径	不保证最优