LC107 · 二叉树的层序遍历 II · 队列分层 + reverse 自底向上
二叉树 · BFS 分层 · 结果反转
LC107 不是从叶子开始遍历，而是先像 LC102 一样从上到下 BFS 分层，再把层结果反转。
核心机制 · LC102 + reverse
LC107 不是从叶子开始遍历，而是先像 LC102 一样从上到下 BFS 分层，再把层结果反转。
- · 先用标准 BFS 按层收集，res 从上到下。
- · 每轮 size := len(queue) 冻结本层，level 从左到右。
- · 最后双指针 reverse res，得到自底向上顺序。
queue 负责一层层向下扩展；level 收集当前层值；res 保存已完成层。BFS 结束后 res 仍是从上到下，只需 reverse 层数组即可满足题目。
- res = append(res, level) // 先从上到下
- for i, j := 0, len(res)-1; i < j; ... // 再反转
普通二叉树节点通常只有 left / right，没有 parent 指针。从叶子往上找父节点并不自然。更简单稳定的方法是：从根节点正常 BFS 收集每一层，最后 reverse 层数组。
每轮 while 开始时，queue 中正好保存当前层所有节点。我们先记录 size，只处理这 size 个节点，因此本轮生成的 level 一定属于同一层，并且顺序是从左到右。
示例树与目标输出
给定二叉树 [3,9,20,null,null,15,7]。题目要求自底向上层序输出：[[15,7],[9,20],[3]]。注意：不是从叶子开始 BFS，而是先正常从上到下分层。
LC107 不是从叶子开始遍历，而是先像 LC102 一样从上到下 BFS 分层，再把层结果反转。
自底向上只是最终呈现顺序；算法主体仍是根出发的标准 BFS。
状态表 · queue / level / res
当前等待处理的节点
当前层收集到的值
已经完成的层结果
二叉树 · BFS 分层
1func levelOrderBottomUp(root *TreeNode) [][]int {2 if root == nil {3 return [][]int{}4 }5 res := [][]int{}6 queue := []*TreeNode{root}7 for len(queue) > 0 {8 size := len(queue)9 level := make([]int, 0, size)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 res = append(res, level)22 }23 for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {24 res[i], res[j] = res[j], res[i]25 }26 return res27}
空树返回空二维数组，不是 nil
size 冻结当前层节点数
内层 for 只处理当前层
BFS 完成后 res 仍是从上到下
双指针 reverse，得到自底向上顺序
- 时间复杂度
- O(n)
- 空间复杂度
- O(n)
每个节点入队、出队各一次；最后 reverse 层数组也是 O(层数) ≤ O(n)。
如果不计算输出数组，队列辅助空间是 O(w)，w 是树的最大宽度；面试中通常说 O(n)。
这题可以看成 LC102 的变体。先用 BFS 按层收集结果，保证每一层内部从左到右；由于题目要求自底向上，只需要最后把二维数组反转。时间 O(n)，空间 O(n)。