Zigzag Level Order Traversal
Mediumjavapythonccppjavascript
Traverse a binary tree level by level, but alternate the direction on each level: the first level left-to-right, the second right-to-left, and so on.
Input Format
The first line contains an integer M, the number of level-order tokens. The second line contains M space-separated tokens (integers or null).
Output Format
Print each level on its own line (in the zigzag direction), values separated by single spaces. Print nothing for an empty tree.
Example 1
Input
7 3 9 20 null null 15 7
Output
3 20 9 15 7
Explanation: Level 0 left-to-right, level 1 right-to-left, level 2 left-to-right.
- 0 <= number of nodes <= 5000
- -1000000000 <= node value <= 1000000000