Problem

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

        C1
       /  \
     C2    C3
    / \   /  \
  C4  C5 C6  C7
 /   / \     / \
C8  C9 C10 C11 C12

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 需要几天，本质就是求树中两个节点之间的边数。

树本身是有父子关系的，但病毒传播不区分方向，既可以从父节点传到子节点，也可以从子节点传到父节点。

所以要把树当成无向图处理。

常见做法是：

1. 遍历整棵树，建立每个节点的邻接关系。
2. 从 src 开始 BFS。
3. 第一次遇到 dst 时，当前层数就是答案。

示例计算

从 C7 到 C8 的路径是：

C7 -> C3 -> C1 -> C2 -> C4 -> C8

一共经过 5 条边，所以答案是：

5

易错点

第一点是只按照子节点方向搜索。
如果从 C7 只往下走，只能到 C11 和 C12，永远到不了 C8。这题必须允许往父节点传播。

第二点是忘记去重。
建成无向图后，C7 可以走到 C3，C3 也可以走回 C7，所以 BFS 必须维护 visited。

第三点是把天数算成节点数。
路径 C7 -> C3 -> C1 -> C2 -> C4 -> C8 有 6 个节点，但传播天数是边数，也就是 5 天。

如果你也在准备 Amazon Front-End 或其他北美大厂面试，csoahelp 可以提供一对一面试辅助服务。我们会根据你的目标岗位，整理高频真题、讲解解题思路、模拟真实面试流程，并帮助你优化表达方式。无论是算法题、前端系统设计，还是 behavioral question，都可以针对性练习，减少盲目刷题，提高面试通过率。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~