Google New Grad 的程式輪常把經典題換個殼子來考你遷移能力。這道題就是經典島嶼題的變體——把網格換成了 0/1 樹狀結構。這篇按 oavoservice 學員的 Google NG 複盤，講清怎麼把「網格島嶼」的 DFS 套路乾淨地遷移到樹上。文末附 VO輔助 / VO代面 的對接路徑，給正在校招、轉碼、後端開發求職的同學一個實戰參考。
一、Google NG 程式輪概覽
| 維度 | 詳情 |
|---|---|
| 形式 | 遠端視訊，單輪約 45 分鐘 |
| 題量 | 1 道程式題 + 追問 |
| 語言 | 自選，Python / Java / C++ 常見 |
| 考察 | 圖與樹遍歷、連通塊、複雜度、溝通 |
| 風格 | 經典題變體，考遷移能力而非默寫 |
Google NG 的題難度集中在 LeetCode 中等。遇到 adapt 過的經典題，先問「原型是哪道」，再把相鄰關係遷移過去，比從零硬想高效得多。
二、題目
經典島嶼題，但稍微 adapt 了一下：在一個由 0 和 1 組成的樹狀結構中，一個 island 被定義為一組被 0 包圍、或位於樹邊界的連續 1。寫一個演算法，求樹中有多少個 island。
三、拆題：把「網格島嶼」遷移到「樹」
經典島嶼題在網格上跑 DFS/BFS，把相鄰的 1 連成一片，數有幾片。這裡結構換成了樹，但核心完全一樣：相鄰關係從「網格的上下左右」變成了「樹的父子邊」。
所以演算法是：遍歷所有節點，遇到一個值為 1 且沒訪問過的節點，就從它出發把整片連通的 1（只沿父子邊、且鄰居也是 1）全部標記訪問，island 計數加一。0 節點天然成為分隔，把不同的 1 連通塊切開。
下面用鄰接表表示樹，val[u] 是節點 u 的 0/1 值：
def count_islands(adj, val, root):
visited = set()
islands = 0
def dfs(u):
visited.add(u)
for v in adj[u]:
if v not in visited and val[v] == 1:
dfs(v) # 只沿 1-1 的邊擴張
# 遍歷所有節點，確保每個 1-連通塊只被起算一次
for u in adj:
if u not in visited and val[u] == 1:
islands += 1
dfs(u)
else:
visited.add(u) # 0 節點也標記，避免重複檢查
return islands
# 1(1)
# / \
# 2(1) 3(0)
# / \
# 4(0) 5(1)
adj = {1: [2, 3], 2: [1, 4], 3: [1, 5], 4: [2], 5: [3]}
val = {1: 1, 2: 1, 3: 0, 4: 0, 5: 1}
print(count_islands(adj, val, 1)) # 2：{1,2} 一片，{5} 一片
時間複雜度：O(V + E)（每節點、每條邊各訪問一次；樹裡 E = V−1，即 O(V)）。空間複雜度：O(V)（visited + 遞迴堆疊）。
提示：樹很深時遞迴會爆堆疊，臨場可以提一句「可改成顯式堆疊的迭代 DFS」，面試官通常很買帳。
四、臨場提醒
- 遇到 adapt 過的經典題，先認出原型（這裡是網格島嶼），再把相鄰關係遷移過去。
- 想清 visited 的邊界：
0節點要不要標記、深遞迴會不會爆堆疊。 - DFS 只沿「鄰居也是 1」的邊擴張，
0節點天然充當連通塊的分隔。 - 先口頭講清「和網格島嶼的唯一區別只是相鄰關係」，再動手，思路更順。
FAQ
Q1：樹狀島嶼和網格島嶼有什麼區別？
核心演算法一樣，都是對連通的 1 做 DFS/BFS 計數。區別只在相鄰關係：網格是上下左右，樹是父子邊。把遍歷的鄰居來源換掉即可，0 節點依然充當分隔。
Q2：為什麼遍歷時也要標記 0 節點？
把 0 節點也加入 visited，可以避免外層迴圈對它重複檢查；它本身不屬於任何島嶼，標記後邏輯更乾淨，也不影響計數。
Q3：樹很深會有什麼問題？
遞迴 DFS 在極深的樹上可能爆堆疊。可以改成用顯式堆疊的迭代 DFS，或限制遞迴深度。面試時主動提這個點，能體現你對邊界的敏感度。
Q4：Google NG 程式輪怎麼高效準備？
按圖與樹遍歷、連通塊 / 並查集、前綴和 / 雜湊、DP 分專題刷，每類限時練並口頭講思路。需要按 Google NG 題型做限時 mock、逐題講解或 VO輔助 / VO代面 全程對接，可以走下面的路徑客製。
正在準備 Google NG 面試？
Google NG 程式輪愛考經典題變體，吃的是遷移能力和清晰表達。oavoservice 提供 Google 全流程陪練：圖與樹遍歷 / 連通塊 / 前綴和 / DP 高頻題限時模擬，拆題與口頭表達逐題打磨，按 NG 校招題型做預測。教練含大廠資深工程師，支援 VO輔助 / VO代面 全程對接。
立即加入微信 Coding0201，取得 Google 真題與陪練。
聯絡方式
- 微信：Coding0201
- Email：[email protected]
- Telegram：@OAVOProxy