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).

ZigzagLevelOrder.java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> answer = new ArrayList<>();     

    zigzagLevelOrderHelper(root, answer, 0);

    return answer;
}

private void zigzagLevelOrderHelper(TreeNode root, List<List<Integer>> answer, int level) {
    if(root == null)
        return;

    if(answer.size() == level)
        answer.add(new ArrayList<Integer>());

    if(level % 2 == 0)
        answer.get(level).add(root.val);
    else 
        answer.get(level).add(0, root.val);

    zigzagLevelOrderHelper(root.left, answer, level + 1);
    zigzagLevelOrderHelper(root.right, answer, level + 1);
}