树与图中等1 种解法
#107二叉树的层序遍历 II
按从叶子层到根层的顺序返回每层节点值。
#二叉树#广度优先搜索
原题
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
解题主线
- 正常 BFS 分层后整体反转即可，节点级顺序不变。
解法 1：BFS 后反转
先得到自顶向下层序结果，最后一次性反转层列表。
-
时间复杂度： O(n)
-
空间复杂度： O(w)，不计返回结果
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 本轮开始时队列前 size 个节点恰好属于同一层，避免混入下一层。
int size = queue.size();
// 层内仍按从左到右收集，最后只反转层列表而不反转节点顺序。
List<Integer> level = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
Collections.reverse(result);
return result;
}
}边界与易错点
- 这是独立的 107 题，不能混在 102 题解法中。
- 逐次向 ArrayList 头部插入会造成额外搬移。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q102_levelOrder.java