A regional office keeps its reporting hierarchy as a binary tree of employee ids. The hierarchy is given in level-order (breadth-first) form as a single line of space-separated tokens, where the token null marks a missing child. The first token is the root; then, following the standard level-order layout, every non-null node contributes exactly two following tokens for its left and right child (each of which may itself be null, and null tokens never contribute further tokens of their own).
An auditor reads the hierarchy level by level, but alternates scanning direction on every level: level 0 (the root) is scanned left-to-right, level 1 is scanned right-to-left, level 2 left-to-right again, and so on, alternating forever.
Print every id in the exact order the auditor encounters them.
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null).
A single line: the node values in zigzag level order, space-separated. If the tree is empty (the input is just null), print an empty line.
Example 1
Input
1 2 3
Expected
1 3 2
Explanation
Level 0 is just the root 1 (left-to-right). Level 1 has 2 (left) then 3 (right); scanned right-to-left it becomes 3 then 2. Output: 1 3 2.
Example 2
Input
5 3 8 1 4 7 9
Expected
5 8 3 1 4 7 9
Explanation
Level 0: 5. Level 1 (right-to-left): 8 3. Level 2 (left-to-right, children of 3 then children of 8): 1 4 7 9. Output: 5 8 3 1 4 7 9.
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 →