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

A country is represented as a tree of cities originating from a single root city.

Each city may be connected to one or more neighboring cities.

A virus starts spreading from city Cm.

Every day, the virus spreads from an infected city to all directly connected neighboring cities.

Given two cities Cm and Cn, determine how many days it will take for the virus to spread from Cm to Cn.

Input

root = C1
src = C7
dst = C8

Output

5

Explanation

Day 0: C7
Day 1: C3, C11, C12
Day 2: C6, C1
Day 3: C2
Day 4: C4, C5
Day 5: C8, C9, C10

C8 becomes infected on Day 5.
Therefore return 5.

这题给出一棵以根节点表示国家城市网络的树，病毒从指定起点城市 src 开始，每天会向所有相邻城市同步扩散一次。要求计算目标城市 dst 第几天被感染，本质上就是在树上求 src 到 dst 的最短路径长度，因为树中任意两点之间路径唯一，传播天数等于边数。常见做法是先建立父指针或把树转成无向图，再从 src 做 BFS 分层遍历，第一次到达 dst 时的层数就是答案。