题目重点：从任意点找一对直径端点，再以两端距离识别所有可能成为某条直径端点的节点；区别只返回任意一对。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入是无权、无向、连通树，节点编号训练版为 0..n−1。
- 返回所有可能作为某条最长路径端点的节点，按编号升序；若面试官只要任意一对，第二次 BFS 的两端即可。
- 单节点树的唯一节点既是起点也是终点，返回 [0]；空图返回 []，题目未明确边界。
解题路线
- 从任意点 0 BFS 得最远点 a；树的最远点可作为某条直径的端点。
- 从 a BFS 得距离 da 和最远点 b，D=da[b] 为树直径长度；再从 b BFS 得 db。
- 树的性质：任意顶点 v 的离心率（到全树最远顶点距离）等于 max(da[v],db[v])，这里 a、b 是一对直径端点。因此 v 是某条直径的端点当且仅当该值等于 D。
- 扫全部节点返回满足条件者。用迭代 BFS 避免深链树递归栈问题；输入若有环或断开，直径的树性质不可直接套。
手动走一遍
星形树中心 0、叶 1/2/3：直径长 2，任意两叶之间都是直径。若只做两次 BFS 可能只得到 1 与 2，漏掉 3；两端距离判据会返回 [1,2,3]。路径树 0−1−2−3 只返回 [0,3]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def all_diameter_endpoints(n: int, edges: list[tuple[int, int]]) -> list[int]:
"""All peripheral vertices in a 0-based undirected tree."""
if n == 0:
if edges:
raise ValueError("edges without nodes")
return []
if len(edges) != n - 1:
raise ValueError("not a tree")
graph = [[] for _ in range(n)]
for u, v in edges:
if not 0 <= u < n or not 0 <= v < n or u == v:
raise ValueError("invalid edge")
graph[u].append(v)
graph[v].append(u)
def bfs(start: int) -> list[int]:
distance = [-1] * n
distance[start] = 0
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if distance[neighbor] == -1:
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
if -1 in distance:
raise ValueError("disconnected input")
return distance
first = bfs(0)
a = max(range(n), key=lambda i: first[i])
distance_a = bfs(a)
b = max(range(n), key=lambda i: distance_a[i])
distance_b = bfs(b)
diameter = distance_a[b]
return [i for i in range(n) if max(distance_a[i], distance_b[i]) == diameter]
if __name__ == "__main__":
assert all_diameter_endpoints(4, [(0, 1), (0, 2), (0, 3)]) == [1, 2, 3]
复杂度
每次 BFS 处理 n 个节点和 n−1 条边，三次仍 O(n) 时间；邻接表与距离数组 O(n) 空间。
易错点与追问
容易失分的边界
- 把一次 DFS 最深节点集合当所有直径端点，根的选择会改变结果。
- 只返回找到的一对 a,b，若题意是所有外围节点则不完整。
- 把树直径长度按节点数和边数混用；代码的 D 是边数。
- 未确认‘所有最两端节点’的返回口径就把训练版解释成唯一原题。
继续深挖
- 若只要求直径长度和任意一对端点，最少几次 BFS？
- 给有权树且权重非负时，如何替换 BFS？
- 若输入是一般图，三次 BFS 的外围节点判据还成立吗？
