546. Best Centres
A telecom company has n relay stations numbered 0 to n - 1, joined by two-way cables listed in edges, where edges[i] = [u, v] links stations u and v. The cables connect all stations without forming a loop.
The head office will be placed in one station, and signals travel outward from it. The height of a choice is the largest number of cables between the office and any other station. Return, in increasing order, all stations that give the smallest possible height. For a single station, the answer is [0].
Example 1
- Input:
- n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[5,6]]
- Output:
- [2,3]
- Explanation:
The longest route 0-1-2-3-5-6 has 6 towns, so its two middle towns 2 and 3 are the best centres, each giving height 3.
Example 2
- Input:
- n = 5, edges = [[4,0],[0,2],[2,1],[1,3]]
- Output:
- [2]
- Explanation:
The chain is 4-0-2-1-3; only the middle town 2 gives the smallest height of 2.
Constraints
1 ≤ n ≤ 2 * 104
edges.length == n - 1, 0 ≤ u, v < n
The edges form a tree. The returned list is sorted in increasing order (it contains one or two stations).
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)