Description
In this Homework, you are given an array to construct a full binary tree in a level order fashion. That is, elements from the left in the array will be filled in the tree level-wise starting from level 1 from left to right.
Below is an example.
Array = [7, 6, 5, 2, 1, 4, 3]
After constructing the tree, you have to complete two tasks.
Task 1. Output the minimum number of operations to make the leaves sorted in increasing order from left to right.
Task 2. Calculate the maximum value of root-to-leaf path and output the value.
Please note that Task 1 and Task 2 are performed on the same “input tree”, i.e., Task 2 is not performed on the resulting tree of Task 1.
Task1:
You could perform “leaf swaps” in the tree’s internal nodes. In a single leaf swap, you can choose any non-leaf node in the tree and swap its leaf node in its subtree. Note that you only swap the leaves but do not swap the internal nodes. For example, assume you have the tree below.
If you perform a leaf swap at node 7, the tree becomes:
Consider another example, assume you have a full binary tree of height 4, and the leaf numbers are 6, 5, 7, 8, 4, 3, 1, 2 (from left to right). Then, you can perform the following leaf swaps (the node that the operation is applied at the current step is highlighted in purple) to make the leaves sorted in increasing order from left to right.
After all the leaf swaps, the value should be like below.
After four leaf swaps, the leaf nodes are in increasing order from left to right, and four is the minimum number of leaf swaps to sort the leaf nodes.
Note that if it is not possible to make the leaf nodes be in increasing order from left to right output -1 as the answer.
Task 2
Please note that Task 2 is performed on the “input tree”, NOT the tree after tree swaps.
Root-to-leaf path goes from the root to a leaf. The value of a root-to-leaf path is the sum of the node keys is passes through. Among all the root-to-leaf paths, you have to find the one with the maximum value and output the value.
For example,
the maximum value of the root-to-leaf paths is 7 + 5 + 4 = 16 (the path 7-5-4). Therefore, you output 16.
Notice: Any kind of STL is not allowed in this homework. (Vector and Stack are allowed)
Input
The first line contains a single integer L (1 <= L <= 15), which indicates the level of the tree.
The second line contains an array A containing the keys of the tree nodes.
-1000000< The key of each node < 1000000
Output
The first line outputs the minimum number of leaf swaps to make the leaves sorted in increasing order from left to right.
The second line outputs the maximum value of the root-to-leaf paths.