# Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

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]
]```

Solution: Use two linked list to represent curr level and the next level. While iterating through the node on the current level, we put the child nodes to next level in order based on if the current level is odd or even.

If current is odd level, so next level should be right->left, so we always insert right node in front of left node.

If current is even level, so next level should be left->right, we always insert left node in front of right node.

```public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
while (!curr.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
while (!curr.isEmpty()) {
TreeNode node = curr.remove();
//current is odd level
//so next level should be right->left
if (res.size() % 2 == 0) {
if (node.left != null) {
}
if (node.right != null) {
}
}
//current is even level
//so next level should be left->right
else {
if (node.right != null) {