难度: Medium
给定一个 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] 之间运行时间: 30 ms
内存: 17.6 MB
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root: return []
ans = []
stack = [root]
while stack:
nxt = []
t = []
for x in stack:
t.append(x.val)
for y in x.children:
nxt.append(y)
ans.append(t.copy())
stack = nxt
return ans
这个题解使用了广度优先搜索（BFS）的思路来实现 N 叉树的层序遍历。具体步骤如下： 1. 首先判断根节点是否为空，如果为空则直接返回空列表。 2. 初始化结果列表 ans 和队列 stack，并将根节点加入队列。 3. 当队列不为空时，进行如下操作： - 初始化下一层节点的队列 nxt 和当前层节点值的临时列表 t。 - 遍历当前队列中的每个节点 x： - 将节点值加入临时列表 t。 - 遍历节点 x 的子节点，将它们加入下一层节点的队列 nxt。 - 将当前层的节点值列表 t 加入结果列表 ans。 - 将下一层节点的队列 nxt 赋值给 stack，开始下一轮循环。 4. 返回结果列表 ans，即为 N 叉树的层序遍历结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return [] # 如果根节点为空，直接返回空列表
ans = [] # 初始化结果列表
stack = [root] # 初始化队列，将根节点加入队列
while stack:
nxt = [] # 初始化下一层节点的队列
t = [] # 初始化当前层节点值的临时列表
for x in stack:
t.append(x.val) # 将当前节点的值加入临时列表
for y in x.children: # 遍历当前节点的子节点
nxt.append(y) # 将子节点加入下一层节点的队列
ans.append(t.copy()) # 将当前层的节点值列表加入结果列表
stack = nxt # 将下一层节点的队列赋值给 stack，开始下一轮循环
return ans # 返回结果列表，即为 N 叉树的层序遍历结果
在本题解中，N 叉树的节点的子节点列表可以包括 null 值，但我们在遍历子节点时并没有特别处理这些 null 值。这是因为在 Python 中，遍历列表时会自动跳过 null 值，不会将它们加入到队列中。因此，算法仅处理有效的非 null 子节点。如果在其他编程环境中必须手动处理 null 值，可以在将子节点加入队列之前添加一个判空条件。
层序遍历要求按照从上到下、从左到右的顺序访问所有节点。使用队列（先进先出）可以自然地实现这一过程：每次从队列的前端移除当前节点，并将其子节点按顺序加入队列的后端。如果使用栈（后进先出），则会导致节点的访问顺序颠倒，无法实现层序遍历。其他数据结构如列表也可以实现，但操作复杂且效率较低。
确实，在树结构特别宽时，队列可能会存储大量的节点，导致内存使用增加。在算法实现时，这种情况是必须考虑的。为了应对可能的内存问题，可以在实际应用中监控内存使用情况，并在树的宽度非常大时考虑使用更高效的数据结构或优化树的结构。此外，也可以通过优化算法逻辑来减少内存的使用，例如通过链接节点而不是复制节点信息。
如果树的结构在遍历过程中发生变化（如添加或删除节点），主要需要关注的是如何保证遍历过程的一致性和正确性。在本算法中，由于我们使用的是队列来控制遍历，如果在遍历过程中修改了树（如添加或删除节点），可能需要同步更新队列中的元素。具体来说，如果添加节点，需要确保这些节点在正确的层次被加入队列；如果删除节点，则需要确保队列中不再引用已删除的节点。这通常要求树结构操作和遍历操作需要良好的同步机制，以防止冲突和错误。