You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
A node is called special if it is an endpoint of any diameter path of the tree.
Return a binary string s of length n, where s[i] = '1' if node i is special, and s[i] = '0' otherwise.
A diameter path of a tree is the longest simple path between any two nodes. A tree may have multiple diameter paths.
An endpoint of a path is the first or last node on that path.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]]
Output: "101"
Explanation:
Example 2:
Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]]
Output: "1000111"
Explanation:
The diameter of this tree consists of 4 edges. There are 4 diameter paths:
The special nodes are nodes 0, 4, 5, 6, as they are endpoints in at least one diameter path.
Example 3:
Input: n = 2, edges = [[0,1]]
Output: "11"
Explanation:
Constraints:
2 <= n <= 105edges.length == n - 1edges[i] = [ai, bi]0 <= ai, bi < nedges represents a valid tree.We first convert the array edges into an adjacency list representation of an undirected graph, where g[u] represents all nodes adjacent to node u.
Next, we can use Breadth-First Search (BFS) to find the diameter endpoints of the tree. The specific steps are as follows:
0), use BFS to find the farthest node a from that node.a, use BFS again to find the farthest node b from node a, as well as the distance array dist1 from node a to all other nodes.b, use BFS to find the distance array dist2 from node b to all other nodes.dist1[b]. For each node i, if dist1[i] or dist2[i] equals the diameter length, then node i is a special node.The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes.
Java
C++
Go
TypeScript
Rust
Practice Find Diameter Endpoints of a Tree with our built-in code editor and test cases.
Practice on FleetCode