Given a binary tree, return thezigzag level ordertraversal 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]
]

Solution: 用deque

  public List<Integer> zigZag(TreeNode root) {
    if (root == null) {
      return new ArrayList<Integer>();
    }
    Deque<TreeNode> deque = new LinkedList<>();
    List<Integer> ans = new ArrayList<>();
    deque.offerLast(root);
    boolean reverse = false;
    while (deque.size() > 0) {
      int size = deque.size();
      for (int i = 0; i < size; i++) {
        TreeNode cur;
        if (reverse) {
          cur = deque.pollFirst();
          if (cur.left != null) {
            deque.offerLast(cur.left);
          }
          if (cur.right != null) {
            deque.offerLast(cur.right);
          }
        } else {
          cur = deque.pollLast();
          if (cur.right != null) {
            deque.offerFirst(cur.right);
          }
          if (cur.left != null) {
            deque.offerFirst(cur.left);
          }
        }
        ans.add(cur.key);
      }
      reverse = !reverse;
    }
    return ans;
  }