426、N叉树的层序遍历

   

1. 输入检查：

   if not root:return []

   • 如果根节点为空，直接返回空列表

2. 初始化：

   result = []
   queue = collections.deque([root])

   • result用于存储最终结果
   • queue初始化包含根节点，使用双端队列实现

3. 主循环：

   while queue:level_size = len(queue)level = []

   • 当队列不为空时继续处理
   • level_size记录当前层的节点数量
   • level用于存储当前层的节点值

4. 处理当前层：

   for _ in range(level_size):node = queue.popleft()level.append(node.val)

   • 处理当前层的每个节点
   • 从队列左侧取出节点
   • 将节点值加入当前层列表

5. 处理子节点：

   for child in node.children:queue.append(child)

   • 将当前节点的所有子节点加入队列（下一层）

6. 存储当前层结果：

   result.append(level)

   • 将当前层的值列表加入最终结果

7. 返回结果：

   return result

   • 返回层次遍历结果

具体例子

考虑以下N叉树：

节点结构

• 节点1：值=1，children=[3,2,4]
• 节点3：值=3，children=[5,6]
• 节点2：值=2，children=[]
• 节点4：值=4，children=[]
• 节点5：值=5，children=[]
• 节点6：值=6，children=[]

代码执行步骤

1. 初始化:

   • result = []
   • queue = [1] (根节点)

2. 第一轮循环:

   • level_size = 1 (队列中只有节点1)
   • level = []
   • 取出节点1，level = [1]
   • 将节点1的子节点(3,2,4)加入队列: queue = [3,2,4]
   • result =[ [1] ]

3. 第二轮循环:

   • level_size = 3 (队列中有3,2,4)
   • level = []
   • 取出节点3，level = [3]
   • 将节点3的子节点(5,6)加入队列: queue = [2,4,5,6]
   • 取出节点2，level = [3,2]
   • 节点2没有子节点
   • 取出节点4，level = [3,2,4]
   • 节点4没有子节点
   • queue = [5,6]
   • result = [[1], [3,2,4]]

4. 第三轮循环:

   • level_size = 2 (队列中有5,6)
   • level = []
   • 取出节点5，level = [5]
   • 节点5没有子节点
   • 取出节点6，level = [5,6]
   • 节点6没有子节点
   • queue = []
   • result = [[1], [3,2,4], [5,6]]

5. 循环结束:

   • 队列为空，退出循环
   • 返回最终结果: [[1], [3,2,4], [5,6]]

最终输出

这个层次遍历的输出结果是：

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

这个结果表示：

• 第一层(根层): 只有节点1
• 第二层: 节点3,2,4
• 第三层: 节点5,6

1. 初始状态：
   • queue = [1]
   • result = []

2. 第一层处理：

   • level_size = 1
   • 处理节点1：
     • level = [1]
     • 加入子节点3,2,4 → queue = [3,2,4]
   • result =[ [1] ]

3. 第二层处理：

   • level_size = 3
   • 处理节点3：
     • level = [3]
     • 加入子节点5,6 → queue = [2,4,5,6]
   • 处理节点2：
     • level = [3,2]
     • 无子节点 → queue = [4,5,6]
   • 处理节点4：
     • level =