Amazon NG VO 每轮先 BQ 再编程，这道"按层连接二叉树 next 指针"是其中一轮的编程题，对应 LeetCode 116/117。这篇按 oavoservice 学员的复盘讲清拆题：树 / 图的题 edge case clarify 非常重要，而这题本质是"按层访问二叉树"+"修改节点内部引用"的结合，并在此基础上看你对 BFS 和 DFS 的掌握。文末附 VO辅助 / VO代面 的对接路径，给正在校招、转码、SDE 求职的同学一个实战参考。
一、题目背景
| 维度 | 详情 |
|---|---|
| 轮次 | Amazon NG VO 编程轮（先 BQ 后编程） |
| 对应 | LeetCode 116 / 117 |
| 语言 | 自选，Python 常见 |
| 考察 | 层序遍历、节点引用修改、BFS/DFS 取舍、edge case |
二、题目
把一棵二叉树每个节点的 next 指针，连成指向同一层的下一个节点（每层最右节点的 next 为 None）。
三、拆题：先 clarify，再选 BFS / DFS
树 / 图的题，edge case 的 clarify 非常重要：是完美二叉树还是普通二叉树？空树？只有根节点？这些先问清楚，再决定写法。
一句话概括这题："按层访问二叉树" + "修改节点内部引用" 两件事的结合，并在此基础上看你对 BFS 和 DFS 的掌握。
- BFS（层序遍历）：最直观，一层一层处理，把每层节点依次串起来。缺点是要用队列，空间 O(w)（w 为最大层宽）。
- DFS / 利用已建好的 next：对完美二叉树可以用上一层已经连好的
next做到 O(1) 额外空间，但逻辑更绕、对普通二叉树要额外处理。
面试里建议先写清楚、稳的 BFS，再口头补充 O(1) 空间的优化方向——既展示掌握度，又不冒险。
BFS 解法（推荐）
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
prev = None
for _ in range(size):
node = q.popleft()
if prev:
prev.next = node # 串起同一层的相邻节点
prev = node
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
# prev 此时是本层最右节点，其 next 默认为 None
return root
时间复杂度：O(n)（每节点入队出队各一次）。空间复杂度：O(w)，最坏 O(n)（队列）。
O(1) 空间优化（完美二叉树）
完美二叉树里，上一层连好 next 后，就能像"链表"一样横向遍历上一层，逐个把下一层的左右孩子串起来，不再需要队列：
def connect_perfect(root):
leftmost = root
while leftmost and leftmost.left:
head = leftmost
while head:
head.left.next = head.right # 同父：左 → 右
if head.next:
head.right.next = head.next.left # 跨父：右 → 下一个父的左
head = head.next
leftmost = leftmost.left
return root
时间复杂度：O(n)。空间复杂度：O(1)（不含输出）。
四、临场提醒
- 树 / 图题先 clarify edge case（树形态、空输入、只有根节点），再选写法。
- 先写稳的 BFS 拿到分，再口头讲 O(1) 空间优化方向，展示对 BFS/DFS 的掌握。
- O(1) 优化只在完美二叉树成立，普通二叉树（LC117）要额外处理"找下一层第一个孩子"。
- 一边写一边说清"为什么这样连"，给面试官清晰的推理过程。
FAQ
Q1：这道题 BFS 和 DFS 怎么选？
BFS 层序最直观、最稳，空间 O(w)；完美二叉树可用上一层已连好的 next 做到 O(1) 额外空间，但逻辑更绕。面试建议先写稳的 BFS，再口头补 O(1) 优化方向，展示掌握度。
Q2：LC116 和 LC117 有什么区别？
116 是完美二叉树（每层填满），可直接用"同父左右 + 跨父"的规则做 O(1) 空间；117 是普通二叉树，孩子可能缺失，需要额外逻辑找下一层的第一个有效孩子，O(1) 解法更繁琐。
Q3：为什么说 edge case clarify 很重要？
树形态（完美 / 普通）、空树、只有根节点都会影响写法和边界。先问清楚能避免写到一半才发现假设错了，也向面试官展示你严谨的工程习惯。
Q4：Amazon NG 编程轮怎么高效准备？
按树 / 图遍历、链表、DP、双指针分专题刷，每类限时练并口头讲思路，同时备好 BQ。需要按 Amazon NG 题型 + BQ 做限时 mock、逐题讲解或 VO辅助 / VO代面 全程对接，可以走下面的路径定制。
正在准备 Amazon NG VO？
Amazon NG 是 BQ + 编程的 loop，编程爱在经典树题上看 BFS/DFS 取舍。oavoservice 提供 Amazon 全流程陪练：树 / 图 / 链表 / DP 高频题限时模拟，edge case clarify 与 O(1) 优化逐题打磨，16 条 LP 的 STAR 故事同步准备。教练含大厂资深工程师与 Bar Raiser 视角，支持 VO辅助 / VO代面 全程对接。
立即添加微信 Coding0201，获取 Amazon 真题与陪练。
联系方式
- 微信：Coding0201
- Email：[email protected]
- Telegram：@OAVOProxy