| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14067 | DS_2023_Quiz_Tree |
|
Description
As the horticulturalist (園藝家), you are good at planting binary trees.
Today, each tree has an acceptable price if the size is large enough.
Given the binary tree T with N nodes, you are asked to calculate the maximum distance between two nodes in T. Besides, you are also asked to print out the postorder traversal sequence of T.
For example:
The maximum distance of this tree is 5 because node 7 and node 6 incur the maximum distance, i.e., going from node 7 to node 6 passes through 5 links.
The postorder traversal sequence of this tree is 7 8 4 5 2 6 3 1. There is no space after the last value.
Notice: Any kind of STL is not allowed in this homework. (Vector and Stack are allowed)
Input
The first line contains an integer N (1 <= N <= 100000), which indicates the integers in the array A representing the tree.
The second line contains an array A, which employs the array representation of the tree. Array A lists the key of each node in level order from left to right, which reserves the room to present a complete binary tree. A key value of -1 indicates that the node is absent in the tree. The index of array A starts from 1. The key of each node is an integer in the range of [1,30000]. (1 <= A[i].val <= 30000)
As an example, the input of the tree above is as follows.
9 (there are 9 integers in the following array)
1 2 3 4 5 -1 6 7 8 (the -1 indicates that the left child of node 3 is absent)
Here is another example to illustrate array A = [1, 2 ,3, -1, 4, 5, 6, -1, -1, 7]
Note that the index of the root node in array A is 1 (with key=1). In addition, since node 2’s left child is absent (represented by the -1 at index 4 in array A), and its two child nodes are also absent (represented by -1, -1 at indices 8, 9 in array A), there are three -1 in array A.
In summary, the input of the above tree is as follows.
10 (there are 10 integers in the following array)
1, 2 ,3, -1, 4, 5, 6, -1, -1, 7
Output
The first line of output is the maximum distance between two nodes in the tree.
The second line is the postorder traversal sequence of the tree.
Note that there is no space after the output and there is no newline after the second output.