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