LC102 · 二叉树的层序遍历 · 工程执行实验室
电梯按楼层接人
题目目标：按层从左到右输出节点值。核心机制：每轮 while 开始时先 size := len(queue) 冻结当前层人数；这一轮只处理 size 个节点，新入队的孩子留给下一层。
核心机制 · size 冻结
层序遍历不是简单 BFS，而是 BFS + 每轮冻结当前层 size。
- · 每轮 while 开始：size := len(queue) 冻结本层人数。
- · 内层 for 只循环 size 次，只处理当前层。
- · 孩子 append 到 queue 尾部，留给下一轮外层循环。
queue 是电梯等候区。每停一层，先看这一层有几个人（size），只让这 size 个人上车；他们带来的下一层朋友排在队尾，等电梯下一次停靠再处理。
- size := len(queue) // 冻结本层
- for i := 0; i < size; i++ // 只扫本层
每次进入外层循环时，queue 中保存的是当前层从左到右的所有节点。记录 size 后，内层循环只弹出这 size 个节点。在弹出当前层节点时加入的孩子，会排在 queue 后面，留给下一轮处理。
输入树：按层从左到右输出节点值
给定二叉树 [3,9,20,null,null,15,7]，目标输出 [[3],[9,20],[15,7]]。先把根节点 3 放入队列，queue=[3]，result=[]。
层序遍历不是简单 BFS，而是 BFS + 每轮冻结当前层 size。
BFS 队列保证先进先出；但仅靠 FIFO 还不够，还需要 size 把「一层」和「下一层」切开。
状态表 · queue / size / level / result
根 3 入队
尚未冻结本层
树 · 按楼层排布
电梯隐喻：每层只接 size 个人1func levelOrder(root *TreeNode) [][]int {2 if root == nil {3 return [][]int{}4 }5 result := [][]int{}6 queue := []*TreeNode{root}7 for len(queue) > 0 {8 size := len(queue)9 level := []int{}10 for i := 0; i < size; i++ {11 node := queue[0]12 queue = queue[1:]13 level = append(level, node.Val)14 if node.Left != nil {15 queue = append(queue, node.Left)16 }17 if node.Right != nil {18 queue = append(queue, node.Right)19 }20 }21 result = append(result, level)22 }23 return result24}
外层 for 负责一层一层推进
size 冻结当前层数量
内层 for 只处理当前层
append child 是为下一层排队
- 时间
- O(n)
- 空间
- O(n)
每个节点入队、出队各一次，共 n 个节点。
辅助队列最坏存一整层节点，层宽 w 最坏为 O(n)；返回结果也占 O(n)。不是 O(1)。
根入队。while 队列非空：先 size := len(queue) 冻结本层人数；内层循环 size 次，每次出队队首、收集值、左右非空孩子入队；把本层 level 追加到 result。时间 O(n)，空间 O(n)（队列最坏 O(n) + 结果 O(n)）。空树返回 [][]。
没有 size 快照只能得到 BFS 一维顺序，无法按层分组输出。
孩子入队后排在 queue 尾部，只有下一轮外层循环才会被 size 圈进本层。
题目要求返回空二维数组 [][]int{}，不是 nil。
队列与结果都需要额外空间，最坏整棵树一层宽为 n，空间是 O(n)。