A plotter head scans a binary tree one level at a time in a back-and-forth (boustrophedon) pattern. Level 0 is read left to right, level 1 right to left, level 2 left to right again, and so on, alternating on every level. Concatenate the values in the order they are read into a single sequence.
Line 1: an integer n, the number of tokens on the next line.
Line 2: n space-separated tokens describing a binary tree in level-order (breadth-first). The first token is the root's value. Reading left to right, keep a queue of already-created nodes; for each node taken from the front of the queue, the next two tokens are its left child then its right child, where the token null marks a missing child. Only non-null children are added to the queue. Trailing null tokens for absent children at the deepest level may be omitted. Every node value is an integer.
A single line: all node values in boustrophedon (zigzag) order, space-separated.
Example 1
Input
7 3 9 20 null null 15 7
Expected
3 20 9 15 7
Explanation
Level 0 [3] left-to-right, level 1 [9,20] reversed to [20,9], level 2 [15,7] left-to-right. Output: 3 20 9 15 7.
Example 2
Input
7 1 2 3 4 5 6 7
Expected
1 3 2 4 5 6 7
Explanation
Level 0 [1], level 1 reversed [3,2], level 2 [4,5,6,7]. Output: 1 3 2 4 5 6 7.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →