Zigzag Level Order Traversal
Traverse a binary tree level by level, alternating the direction of traversal at each level.
Input format
The first line contains level-order tokens, where N denotes a null node.
Output format
Print zigzag level-order: level 0 left→right, level 1 right→left, alternating.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
27 3 49 88 30 55 53 36 62 65 10 33 22 N 11 17 73 N 79 39 N N 93 N 57 N N N N N N N N 20 N 35 N 19 15 N 45Expected output
27
49 3
88 30 55 53
11 22 33 10 65 62 36
17 73 79 39 93 57
45 15 19 35 20
Example 2
Input
91 3 12 N 49 N 63Expected output
91
12 3
49 63