Problem Statement |
| |
Trees are important data structures in programming. In this problem, you will be given a tree that was constructed from a fully connected undirected acyclic graph with exactly N nodes. First, a distinct number between 0 and N-1, inclusive, was assigned to each node. Then, one of the nodes was selected to be the root of the tree. Finally, each non-root node was assigned its neighbor closest to the root as its parent.
You will be given the tree as a int[], where the i-th element is the parent of the i-th node, or -1 if the i-th node is the root (indices are 0-based). A tree is considered equivalent to this tree if it can be constructed from the same original graph using the method described above. This means you can renumber the nodes and select a different node as the root (see examples for clarification). Return a int[] containing the equivalent tree that comes first lexicographically. A int[] a1 comes before int[] a2 lexicographically if a1 has a smaller value at the first element where they differ.
|
| |
Definition |
| | | Class: | NormalizingTrees | | Method: | normalize | | Parameters: | int[] | | Returns: | int[] | | Method signature: | int[] normalize(int[] tree) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | tree will contain between 1 and 50 elements, inclusive. |
| - | Each element of tree will be between -1 and N-1, inclusive, where N is the number of elements in tree. |
| - | Exactly one element of tree will be -1. |
| - | tree will represent a connected acyclic graph. |
| |
Examples |
| 0) | |
| | | Returns: {-1, 0, 0, 0, 1, 4 } | This is the original drawing (with 2 as the root):
2
/ \
0 4
/ / \
1 3 5
The renumbering gives this:
1
/ \
4 0
/ / \
5 2 3
and taking the new 0 as the root gives the answer:
0
/ | \
1 2 3
|
4
|
5
|
|
|
| 1) | |
| | | Returns: {-1, 0, 0, 1, 2 } | | This is a simple path of length 5. Selecting the middle node as root and renumbering gives the lexicographically first representation. |
|
|
| 2) | |
| | | Returns: {-1, 0, 0, 0, 0, 0 } | | This tree has the shape of a star (one center node with 5 nodes connected to it). |
|
|
| 3) | |
| | {10,9,6,10,6,9,7,-1,9,7,7,10,6} |
| Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6 } | |
|
| 4) | |
| | {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6} |
| Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6 } | |
|