public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    if (root == null)
      return results;
    LinkedList<TreeNode> q = new LinkedList<TreeNode>();
    q.add(root);
    boolean left = false;
    while (!q.isEmpty()) {
      int size = q.size();
      List<Integer> result = new ArrayList<Integer>();
      for (int i = 0; i < size; i++) {
        TreeNode n = q.poll();
        result.add(n.val);
        if (left) {
          if (n.right != null) {
            q.add(0, n.right);
          }
          if (n.left != null) {
            q.add(0, n.left);
          }
        } else {
          if (n.left != null) {
            q.add(0, n.left);
          }
          if (n.right != null) {
            q.add(0, n.right);
          }

        }
      }
      results.add(result);
      left = !left;
    }
    return results;
  }