My accepted JAVA solution
public class Solution {\n        public List<List<Integer>> zigzagLevelOrder(TreeNode root) \n        {\n            List<List<Integer>> sol = new ArrayList<>()
    public class Solution {\n        public List<List<Integer>> zigzagLevelOrder(TreeNode root) \n        {\n            List<List<Integer>> sol = new ArrayList<>();\n            travel(root, sol, 0);\n            return sol;\n        }\n        \n        private void travel(TreeNode curr, List<List<Integer>> sol, int level)\n        {\n            if(curr == null) return;\n            \n            if(sol.size() <= level)\n            {\n                List<Integer> newLevel = new LinkedList<>();\n                sol.add(newLevel);\n            }\n            \n            List<Integer> collection  = sol.get(level);\n            if(level % 2 == 0) collection.add(curr.val);\n            else collection.add(0, curr.val);\n            \n            travel(curr.left, sol, level + 1);\n            travel(curr.right, sol, level + 1);\n        }\n    }\n\n1.  O(n) solution by using LinkedList along with ArrayList.  So insertion in the inner list and outer list are both O(1),\n2.  Using DFS and creating new lists when needed.\n\nshould be quite straightforward.  any better answer?
['Java']