手撕:二叉树的层序遍历。
五个经典回答示范
「层序遍历用队列 BFS:根入队,每轮取当前队列长度 size 作为本层节点数,循环 size 次出队并把子节点入队——size 快照保证按层分组。变体只需要在层内做加工:之字形加个方向标志交替反转、右视图取每层最后一个、锯齿层次按层奇偶决定收集顺序。」
function levelOrder(root) { if (!root) return []; const res = [], q = [root]; while (q.length) { const size = q.length, level = []; for (let i = 0; i < size; i++) { const n = q.shift(); level.push(n.val); if (n.left) q.push(n.left); if (n.right) q.push(n.right); } res.push(level); } return res; } 时间 O(n) 空间 O(宽度)。
之字形:层序结果按层奇偶 reverse 或用双端队列头尾交替插入;每层最大值:level 内直接求 max;最小深度:BFS 首个叶子所在层——这也是 BFS 求最短路径的模板;锯齿遍历注意反转的是收集顺序不是入队顺序。讲变体时点出共同点:层内处理逻辑替换,外层框架不变。
必测:空树、单节点、只有左链或右链的退化树(每层一个节点)、满树、值有重复。JS 里 shift 是 O(n),数据量大时可换头指针索引或用链表实现队列——主动提这个细节是加分项。
错误一:不用 size 快照,出队一个入队两个,结果混层。错误二:空树没判,null 访问 val 报错。错误三:DFS 也能做但没传深度参数,节点挂错层。点评:这题考的是队列状态管理,混层说明没有理解 size 快照为什么存在。
- 打开 模拟练习,选择「算法工程师」方向,限时 3 分钟作答本题。
- 对照上方答题框架,逐点检查:哪些要素没覆盖、哪里表达啰嗦。
- 用自己项目的真实经历替换框架中的占位内容,重讲一遍并录音回听。
这类题在真实面试中常被追问细节,
建议进入限时模式练一遍。