Mid/Senior
Tree Diameter
You are given an undirected tree represented by an array edges, where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i.
The tree has edges.length + 1 nodes labeled from 0 to edges.length.
The diameter of a tree is the length of the longest path between any two nodes in the tree. The length of a path is the number of edges in that path.
Return the diameter of the tree.
Example 1
Input
edges = [[0,1],[0,2]]Output
2The longest path is from node 1 to node 2 through node 0, which has length 2.
Example 2
Input
edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]Output
4One longest path is from node 3 to node 5 through nodes 2, 1, and 4, which has length 4.
Constraints
- 0 <= edges.length < 10^4
- edges[i].length == 2
- 0 <= edges[i][0], edges[i][1] <= edges.length
- edges[i][0] != edges[i][1]
- The given edges form a valid tree.