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.Loading editor...
3 [[0,1],[1,2]]