Amazon OA 面试真题解析：树形城市网络中的病毒传播天数

题目描述

一个国家由以单个根城市为起点的树表示，每个城市可连接若干相邻城市。病毒从根城市开始，每天传播到所有相邻城市，求感染整棵树所需的天数。

解题思路

病毒每天沿边扩散一层，感染全部城市所需天数就是根节点到最远节点的距离（树的深度）。用 BFS 按层扩展，或用 DFS 求每个子树高度再取最大值。

from collections import deque

def spread_days(n, edges, root=0):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    days = -1
    seen = {root}
    q = deque([root])
    while q:
        days += 1
        for _ in range(len(q)):
            u = q.popleft()
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    q.append(v)
    return days

复杂度与易错点

BFS 遍历 O(n)，空间 O(n)。树的边是双向的，遍历时要用 visited 防止沿父边回头导致死循环；根不固定时，先找直径或按题意指定根再算深度。

FAQ

为什么感染天数等于树的深度而不是节点数？

病毒每过一天沿边传播一层，第 d 天感染深度 d 以内的所有节点，所以全部感染所需天数就是最大深度。

参考来源

• LeetCode 104 — Maximum Depth of Binary Tree
• LeetCode 863 — All Nodes Distance K in Binary Tree

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。