面试手撕二叉树层序遍历:代码模板与七种常见变形
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 手撕:二叉树的层序遍历,按层返回二维数组。
- 变体:之字形(锯齿形)层序遍历,奇数层从左到右、偶数层从右到左。
- 变体:返回每一层的最大值(或平均值)。
- 变体:二叉树的右视图,即从右侧能看到的节点。
- 变体:求二叉树的最大宽度(含中间的空节点)。
- 变体:自底向上的层序遍历。
- 变体:填充每个节点的下一个右侧节点指针。
- 追问:层序遍历与深度优先遍历的取舍,空间复杂度怎么算?
- 追问:N 叉树的层序遍历怎么写?
- 追问:为什么必须用队列?能不能用两个栈实现?
《参考解析》
标准模板只有一件事:在每一层开始时把队列长度固定住。 层序遍历的常见错误不是逻辑,而是把「当前层」和「下一层」混在一起。正确写法是每轮先记下 size = queue.size(),这一轮只弹出 size 个节点,弹出的同时把它们的子节点入队,子节点属于下一轮。外层循环控制层数,内层循环控制本层节点,这样天然得到按层分组的二维结果。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res; // 空树直接返回,别让后面的 queue.peek 抛空指针
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size(); // 关键:本层节点数在这一刻确定
List<Integer> level = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
level.add(cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
res.add(level);
}
return res;
}
时间复杂度 O(n),每个节点进出队各一次;空间复杂度 O(w),w 为树的最大宽度(完全二叉树最后一层约 n/2),退化成链时是 O(1)。这一点是追问的高频考点:BFS 的空间与宽度相关,DFS 的空间与高度相关,两种写法在同一棵树上可能差一个数量级。
之字形遍历不要真去反转。 两种写法:一是按层收集后,对奇数层做 Collections.reverse,代码最短、代价是多一次 O(w) 的反转;二是用双端队列,奇数层从尾部取、偶数层从头部取,子节点的插入方向随层交替。面试时先说第一种,再补第二种,说明你知道代价在哪。
右视图就是每层的最后一个节点。 用标准模板,在内层循环里判断 i == size - 1 时把值加入结果。等价地也可以用 DFS 按「先右后左」遍历并记录首次到达的深度,两种写法都要能写。
最大宽度考的是编号而不是计数。 给每个节点按完全二叉树的规则编号(左子 2i、右子 2i+1),每层宽度等于「该层最右编号 − 最左编号 + 1」。编号会随深度指数增长,深度超过 60 就会溢出 int,必须用 long。很多人第一反应是数队列里的节点数,那只统计了存在的节点,题目要的是含空位的宽度,两者不是一回事。
自底向上层序先按标准模板得到自上而下的结果,最后整体反转,或用 LinkedList 每层头插。填充右侧指针在层序遍历的框架里做:同一层内,当前节点出队时把它的 next 指向队列中下一个同层节点(即本层未处理完时的队首),最后一个指向 null;进阶要求 O(1) 空间时改用已建立的 next 指针遍历下一层。
队列是层序的本质,两个栈只是变形。 层序要求「先进先出」地按距离根的层级处理,队列天然满足;用两个栈模拟也能做(一个栈存当前层、一个栈存下一层),但代码更绕、并不更快。面试官问这句是看你是否理解 BFS 的语义,而不是背模板。
边界要有意识地报出来。 空树返回空列表而不是 [[]];单节点返回一层;只有左子树或只有右子树的斜树不会跳过空位(层序按实际存在的节点输出);节点值可能为负,用最大值初始化时不能用 0。这几条主动说明,能省掉面试官逐个追问。
N 叉树把「左右子节点入队」换成遍历 children 列表依次入队即可,模板完全不变。凡是「按层处理」的题——层平均值、每层节点数、找堂兄弟、判断完全二叉树——都是这个模板加一行判断。