二叉树的层序遍历 II

怎样从“层序 II 自底向上输出。”推导出 二叉树 · BFS 分层 · 结果反转，并证明每次状态变化都不会漏掉答案？

中心结论：标准 BFS 收集层，最后 reverse 结果。

按层序从下到上遍历一颗树。

在本站主例中，层序 II 自底向上输出。

算法最终需要得到或观察：[[15,7],[9,20],[3]]。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 queue、level、res 三变量 + reverse。
3. 3转移每一步按照 标准 BFS 收集层，最后 reverse 结果。
4. 4收尾读取 [[15,7],[9,20],[3]]。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：queue、level、res 三变量 + reverse。

标准 BFS 收集层，最后 reverse 结果。

执行过程中持续维护：queue、level、res 三变量 + reverse。

正确性依赖以下不变量：每轮 while 开始时 queue 中正好保存当前层所有节点；记录 size 后只处理这 size 个，level 从左到右。

面试时可以压缩为：这题可以看成 LC102 的变体。先用 BFS 按层收集结果，保证每一层内部从左到右；由于题目要求自底向上，只需要最后把二维数组反转。时间 O(n)，空间 O(n)。

落到当前题，执行机制可以压缩为：标准 BFS 收集层，最后 reverse 结果。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入层序 II 自底向上输出。 因为：标准 BFS 收集层，最后 reverse 结果。
2. 2BFS 队列层序根入队。 因为：FIFO 保证同层顺序。
3. 3出队访问 9访问并把左右孩子入队。 因为：size 快照划分层界。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5出队访问 20访问并把左右孩子入队。 因为：size 快照划分层界。
6. 6出队访问 15访问并把左右孩子入队。 因为：size 快照划分层界。
7. 7层序: [3] | [9,20] | [15,7]队列为空。 因为：O(n) BFS。
8. 8收尾与复杂度[[15,7],[9,20],[3]]。 因为：时间 O(n) · 空间 O(n)。标准 BFS 收集层，最后 reverse 结果。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func levelOrderBottom(root *TreeNode) [][]int {
	tmp := levelOrder(root)
	res := [][]int{}
	for i := len(tmp) - 1; i >= 0; i-- {
		res = append(res, tmp[i])
	}
	return res
}

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	queue := []*TreeNode{}
	queue = append(queue, root)
	curNum, nextLevelNum, res, tmp := 1, 0, [][]int{}, []int{}
	for len(queue) != 0 {
		if curNum > 0 {
			node := queue[0]
			if node.Left != nil {
				queue = append(queue, node.Left)
				nextLevelNum++
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
				nextLevelNum++
			}
			curNum--
			tmp = append(tmp, node.Val)
			queue = queue[1:]
		}
		if curNum == 0 {
			res = append(res, tmp)
			curNum = nextLevelNum
			nextLevelNum = 0
			tmp = []int{}
		}
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="level-order", values=[3,9,20,15,7]
    //    期望：[[15,7],[9,20],[3]]。
    //
    // 2. 失败 / 未命中
    //    检查：不必真从叶子 BFS 向上；普通二叉树无 parent 指针，reverse 更简单稳定。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC102 层序；LC199 右视图
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意层序 II 自底向上输出。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化标准 BFS 收集层，最后 reverse 结果。
4. 4证明每轮 while 开始时 queue 中正好保存当前层所有节点；记录 size 后只处理这 size 个，level 从左到右。
5. 5复杂度时间 O(n)，空间 O(n)