349. Zigzag Level Order
Print the tree row by row, but alternate the direction: the first row left to right, the second right to left, the third left to right, and so on.
4
/ \
2 6 zigzag is 4, then 6 2, then 1 3 5 7
/ \ / \ so the output is 4 6 2 1 3 5 7
1 3 5 7
Do not try to alternate the order things are pushed. That is fiddly and easy to get wrong. Collect each row in the ordinary left-to-right way, and reverse the rows at odd depths before printing.
The root's row counts as depth 0 and is not reversed.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print the values in zigzag level order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.