# Question

Formatted question description: https://leetcode.ca/all/103.html

103	Binary Tree Zigzag Level Order

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9  20
/  \
15   7
return its zigzag level order traversal as:
[
,
[20,9],
[15,7]
]

@tag-tree



# Algorithm

Since the number of nodes in each layer is known, that is, the number of elements in the queue, the size of the array can be initialized directly. At this time, a variable leftToRight is used to mark the order.

The initial value is true. When this variable is true, the position that is added to the array is i itself. If the variable is false, it is added to the position of size-1-i. This is directly equivalent to flipping the array. After traversing each level, you need to flip the leftToRight variable, and don’t forget to add oneLevel to the result.

Java