429. N 叉树的层序遍历

🟠   🔖  树 广度优先搜索  🔗 力扣 LeetCode

题目

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

Input: root = [1,null,3,2,4,null,5,6]

Output: [[1],[3,2,4],[5,6]]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

Constraints:

• The height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, 10^4]

题目大意

给定一个 N 叉树，返回其节点值的 层序遍历 。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入： root = [1,null,3,2,4,null,5,6]

输出：[[1],[3,2,4],[5,6]]

示例 2：

输入： root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

• 树的高度不会超过 1000
• 树的节点总数在 [0, 10^4] 之间

解题思路

1. 使用 BFS 进行层序遍历

   • 采用 队列 (queue) 进行层序遍历，每次处理当前层的所有节点，并将它们的值存入结果数组 res。

2. 循环遍历队列

   • 每次遍历当前层的所有节点，存入 level 数组，并将其所有子节点加入队列。

3. 存储结果

   • 每一层遍历完后，将 level 存入 res。

复杂度分析

• 时间复杂度：O(n)，每个节点只进队列和出队列一次，总共有 n 个节点。
• 空间复杂度：O(n)，在最坏情况下，队列可能存储所有叶子节点。

代码

/**
 * @param {_Node|null} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
	let res = [];
	if (!root) return res;

	let queue = [root];

	while (queue.length) {
		const len = queue.length;
		let level = [];
		for (let i = 0; i < len; i++) {
			const node = queue.shift();
			level.push(node.val);
			for (let child of node.children) {
				queue.push(child);
			}
		}
		res.push(level);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
102	二叉树的层序遍历	[✓]	树 广度优先搜索 二叉树	🟠	🀄️ 🔗
589	N 叉树的前序遍历	[✓]	栈 树 深度优先搜索	🟢	🀄️ 🔗
590	N 叉树的后序遍历	[✓]	栈 树 深度优先搜索	🟢	🀄️ 🔗
2039	网络空闲的时刻		广度优先搜索 图 数组	🟠	🀄️ 🔗