Java iterative and recursive solutions.
    \n    // bfs \n    public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {\n        List<List<Integer>> ret = new ArrayList<>();\n        Queue<TreeNo
        \n    // bfs \n    public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {\n        List<List<Integer>> ret = new ArrayList<>();\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.add(root);\n        int l = 0;\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            List<Integer> level = new ArrayList<>();\n            for (int i = 0; i < size; i++) {\n                TreeNode node = queue.poll();\n                if (node != null) {\n                    level.add(node.val);\n                    queue.add(node.left);\n                    queue.add(node.right);\n                }\n            }\n            if (!level.isEmpty()) {\n                if (l % 2 == 1) {\n                    Collections.reverse(level);\n                }\n                ret.add(level);\n            }\n            l++;\n        }\n        return ret;\n     }\n     \n     // dfs recursively\n     public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {\n         List<List<Integer>> ret = new ArrayList<>();\n         dfs(root, 0, ret);\n         return ret;\n     }\n     \n     private void dfs(TreeNode node, int l, List<List<Integer>> ret) {\n         if (node != null) {\n             if (l == ret.size()) {\n                 List<Integer> level = new ArrayList<>();\n                 ret.add(level);\n             }\n             if (l % 2 == 1) {\n                ret.get(l).add(0, node.val);  // insert at the beginning\n             } else {\n                ret.get(l).add(node.val);\n             }\n             dfs(node.left, l+1, ret);\n             dfs(node.right, l+1, ret);\n         }\n     }\n     \n     // dfs iteratively\n     // import javafx.util.Pair;\n     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n         List<List<Integer>> ret = new ArrayList<>();\n         Deque<Pair<TreeNode, Integer>> stack = new LinkedList<>();\n         stack.push(new Pair(root, 0));\n         while (!stack.isEmpty()) {\n             Pair<TreeNode, Integer> p = stack.pop();\n             TreeNode node = p.getKey();\n             int l = p.getValue();\n             if (node != null) {\n                if (l == ret.size()) {\n                    ret.add(new ArrayList<>());\n                }\n                if (l % 2 == 1) {\n                    ret.get(l).add(0, node.val);\n                } else {\n                    ret.get(l).add(node.val);\n                }\n                stack.push(new Pair(node.right, l+1));\n                stack.push(new Pair(node.left, l+1));\n             }\n         }\n         return ret;\n     }
['Depth-First Search', 'Breadth-First Search', 'Java']