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,null,null,15,7],
3
/
9  20
/
15   7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

Runtime: 1 ms, faster than 90.32% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
Memory Usage: 37.1 MB, less than 100.00% of Java online submissions for Binary Tree Zigzag Level Order Traversal.

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (null == root) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
int currentLevelCount = 1, nextLevelCount = 0;
boolean direction = true;
while (!queue.isEmpty()) {
List<Integer> curLevelElems = new ArrayList<>(currentLevelCount);
for (int i = 0; i < currentLevelCount; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
nextLevelCount++;
}
if (node.right != null) {
nextLevelCount++;
}
if (direction) {