Find Min Distance to Furthest Node (Google Tokyo)
Google● MediumINTERNOAProblem statement
You are given a tree-shaped undirected graph consisting of n nodes labeled 1...n and n-1 edges. The i-th edge connects nodes edges[i][0] and edges[i][1] together.
For a node x in the tree, let d(x) be the distance (the number of edges) from x to its farthest node. Find the min value of d(x) for the given tree.
The tree has the following properties:
- It is connected.
- It has no cycles.
- For any pair of distinct nodes
xandyin the tree, there's exactly 1 path connectingxandy.
Function
findMinDistanceToFurthestNode(n: int, edges: int[][]) → int
Complete the function findMinDistanceToFurthestNode in the editor.
findMinDistanceToFurthestNode has the following parameters:
int n: the number of nodesint edges[n-1][2]: an array ofn-1edges where eachedges[i]contains two integers representing an edge connecting the nodes
Returns int: the minimum distance to the furthest node
Examples
Example 1
n = 6edges = [[1, 4], [2, 3], [3, 4], [4, 5], [5, 6]]return = 2
No explanation available.
Example 2
n = 6edges = [[1, 3], [4, 5], [5, 6], [3, 2], [3, 4]]return = 2
No explanation available.
Example 3
n = 2edges = [[1, 2]]return = 1
No explanation available.
Example 4
n = 10edges = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10]]return = 5
No explanation available.
Example 5
n = 10edges = [[7, 8], [7, 9], [4, 5], [1, 3], [3, 4], [6, 7], [4, 6], [2, 3], [9, 10]]return = 3
No explanation available.
Constraints
1 <= n <= 10^5edges.length == n - 1- Every edge joins two distinct labels in
[1, n], and the graph is a tree.