Loading...
Loading...
Loading...
For the annual function, the students of a class stand on tiered steps in the shape of a tree. Each student has at most two students on the step below. Vikram stands to the right of the steps and looks at them from the side.
On every step he sees only the student who is furthest to the right. Print the roll numbers he sees, from the top step down.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. For example, 1 2 3 N 4 is root 1 with children 2 and 3, and 4 is the right child of 2. The tree has at least one node.Example 1
Input
1 2 3 N 5 N 4
Output
1 3 4
The rightmost nodes are 1, then 3, then 4.
Example 2
Input
1 2 3 4
Output
1 3 4
Level 3 has only 4. It hangs on the left side, but nothing stands to its right.
Try the problem first. Open one hint at a time.
Following only right children is not enough: on a deep level the only node may sit on the left.
Go through the tree level by level. The last node of each level is the one seen from the right.
Another way: visit nodes depth-first, right child before left. The first node you reach on each new depth is the answer for that depth.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor