Binary Tree Zigzag Level Order Traversal

Problem:

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

Analysis:
Use a flag to mark whether to reverse or not.

Solution:

 /**  
  * 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) {  
     Queue<TreeNode> queue = new LinkedList<>();  
     List<List<Integer>> res = new ArrayList<>();  
     Boolean reverse = false;  
     if (root == null) return res;  
     queue.offer(root);  
     while (!queue.isEmpty()) {  
     List<Integer> temp = new ArrayList<>();  
     int size = queue.size();  
     for (int i = 0; i < size; i++) {  
      TreeNode cur = queue.poll();  
      temp.add(cur.val);   
      if (cur.left != null) queue.offer(cur.left);  
      if (cur.right != null) queue.offer(cur.right);  
     }  
     if (reverse) {  
       Collections.reverse(temp);  
     }  
     reverse = !reverse;  
     res.add(temp);  
     }  
     return res;  
   }  
 }