Loading...
Loading...
Loading...
A family history app saves each family tree as one line of text and opens it again later. The saved form is the preorder list with a # for every missing child: write the node, then the saved form of its left part, then the saved form of its right part. A missing node is just #.
For example, the tree 1 2 3 N 4 is saved as 1 2 # 4 # # 3 # #. Write both directions. If the first line is save, read a tree in level order and print its saved form. If it is restore, read a saved form and print the tree in level order.
save or restore. For save, the second line is a tree in level order: values separated by single spaces, N for no node, children listed only for real nodes, and N tokens at the end may be left out. An empty tree is N. For restore, the second line is a saved form, with tokens separated by single spaces.save: one line with the saved form, tokens separated by single spaces. For restore: one line with the tree in level order, with every N at the end of the line removed. An empty tree prints N.Example 1
Input
save 1 2 3 N 4
Output
1 2 # 4 # # 3 # #
1, then the left part 2 # 4 # #, then the right part 3 # #.
Example 2
Input
restore 1 2 # 4 # # 3 # #
Output
1 2 3 N 4
The same tree back in level order. The two N children of 3 and of 4 at the end are not printed.
Try the problem first. Open one hint at a time.
Saving is a preorder walk that writes # whenever it reaches a missing child.
Restoring reads the tokens one at a time in the same order. A # gives null. A number gives a node whose left part and then right part are read the same way.
For the level-order output, walk level by level and write N for each missing child of a real node. At the end, remove the N tokens at the end of the line.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor