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