Given a tree with N nodes, a node is called special if it is an end-point of any of the diameters of the tree. For all the nodes of the tree, find if it is special or not. Thus, return a binary array, where the ith value of the array will be 1, in case the ith node is special. Else, the ith value of the array will be 0.
Note: The diameter of a tree is defined as the number of edges in the longest path of the tree.
For example, consider the tree given below:
We can see that this tree has only one diameter, which is the unique path between nodes 1 and 3. Then length of the diameter is 2.
The end-points of the diameter are 1 and 3. Hence, nodes 1 and 3 are considered special, while node 2 is not considered a special node of the tree.
Function Description
Complete the function isSpecial in the editor.
isSpecial has the following parameter(s):
tree_nodes: The number of nodes in the tree.tree_from: The nodes from which the edge is incident onto the other nodetree_to: The nodes on which the edge is incident
Returns
int[n]: an integer array of size N, where the nth value of the array is 1, in case the nth node is special.
Else, the nth value will be 0.
Example 1:
Input: tree_nodes = 7, tree_from = [1, 2, 3, 3, 1, 1], tree_to = [2, 3, 4, 5, 6, 7]
Output: [0, 0, 0, 1, 1, 1, 1]
Explanation:We have four diameters in this tree, which are the unique paths between the nodes (6,5), (6,4), (7,5) and (7,4). The special nodes are nodes 4,5,6,7 (since they are the end-points of at least one of the diameters of the given tree).
1 <= tree_nodes <= 10^5|tree_from| = |tree_to| = tree_nodes - 11 <= tree_fromi, tree_toi <= tree_nodes
input:
output: