2649. 嵌套数组生成器

🟠   🔗 力扣 LeetCode

题目

Given a multi-dimensional array of integers, return a generator object which yields integers in the same order as inorder traversal.

A multi-dimensional array is a recursive data structure that contains both integers and other multi-dimensional arrays.

inorder traversal iterates over each array from left to right, yielding any integers it encounters or applying inorder traversal to any arrays it encounters.

Example 1:

Input: arr = [[[6]],[1,3],[]]

Output: [6,1,3]

Explanation:

const generator = inorderTraversal(arr);

generator.next().value; // 6

generator.next().value; // 1

generator.next().value; // 3

generator.next().done; // true

Example 2:

Input: arr = []

Output: []

Explanation: There are no integers so the generator doesn't yield anything.

Constraints:

• 0 <= arr.flat().length <= 10^5
• 0 <= arr.flat()[i] <= 10^5
• maxNestingDepth <= 10^5

Can you solve this without creating a new flattened version of the array?

题目大意

现给定一个整数的 多维数组 ，请你返回一个生成器对象，按照 中序遍历 的顺序逐个生成整数。

多维数组 是一个递归数据结构，包含整数和其他 多维数组 。

中序遍历 是从左到右遍历每个数组，在遇到任何整数时生成它，遇到任何数组时递归应用 中序遍历 。

示例 1：

输入： arr = [[[6]],[1,3],[]]

输出：[6,1,3]

解释：

const generator = inorderTraversal(arr);

generator.next().value; // 6

generator.next().value; // 1

generator.next().value; // 3

generator.next().done; // true

示例 2：

输入： arr = []

输出：[]

解释： 输入的多维数组没有任何参数，所以生成器不需要生成任何值。

提示：

• 0 <= arr.flat().length <= 10^5
• 0 <= arr.flat()[i] <= 10^5
• maxNestingDepth <= 10^5

解题思路

要实现一个生成器，用于对一个整数的多维数组进行中序遍历，可以使用递归的方法。这个生成器会遍历数组中的每个元素，如果遇到整数，则生成该整数；如果遇到另一个数组，则递归地调用自身来处理该数组。

1. 生成器函数：

   • inorderTraversal 是一个生成器函数，使用 function* 定义。
   • 它接受一个参数 arr，该参数是一个多维数组。

2. 遍历数组：

   • 使用 for...of 循环遍历数组中的每个元素。
   • Array.isArray(item) 用于检查当前元素是否是一个数组。

3. 递归生成：

   • 如果当前元素是数组，则使用 yield* 关键字递归调用 inorderTraversal(item)，这会生成该子数组中的所有元素。
   • 如果当前元素是整数，则使用 yield 直接生成该整数。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组中所有整数的数量，因为每个整数都会被生成一次。
• 空间复杂度：O(d)，其中 d 是递归的最大深度，这里主要用于保存函数调用栈。

代码

/**
 * @param {Array} arr
 * @return {Generator}
 */
var inorderTraversal = function* (arr) {
	for (let item of arr) {
		if (Array.isArray(item)) {
			// 如果当前项是数组，则递归调用生成器
			yield* inorderTraversal(item);
		} else {
			// 如果当前项是整数，直接生成该值
			yield item;
		}
	}
};

/**
 * const gen = inorderTraversal([1, [2, 3]]);
 * gen.next().value; // 1
 * gen.next().value; // 2
 * gen.next().value; // 3
 */

相关题目

题号	标题	题解	标签	难度	力扣
2625	扁平化嵌套数组	[✓]		🟠	🀄️ 🔗
2648	生成斐波那契数列	[✓]		🟢	🀄️ 🔗
2650	设计可取消函数	[✓]		🔴	🀄️ 🔗