Big Brain Approach || JAVA || 200 IQ
Intuition\nI just took the normal level order traversal, stored each level in a different list, inside the main list and then reversed all the alternate lists.\
# Intuition\nI just took the normal level order traversal, stored each level in a different list, inside the main list and then reversed all the alternate lists.\n\n# Approach\n1. Use a queue to perform a level order traversal of the tree. This allows us to process each level of the tree one at a time.\n2. For each level, store the node values in a list and add that list to the result.\n3. After obtaining the result, iterate through the lists in the result. For every alternate list (i.e., indices 1, 3, 5, etc.), reverse the list to achieve the zigzag order.\n4. Return the final list of lists.\n\n# Complexity\n- Time complexity: $$O(n)$$, where $$n$$ is the number of nodes in the binary tree. We visit each node once during the traversal.\n  \n- Space complexity: $$O(n)$$ for storing the result and the queue, which may contain up to $$n$$ nodes in the worst case.\n\n# Code\n```java\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> ans = ques(root);\n\n        for (int i = 1; i < ans.size(); i += 2) {\n            Collections.reverse(ans.get(i)); \n        }\n    \n        return ans;\n    }\n        \n    public List<List<Integer>> ques(TreeNode root) {\n        List<List<Integer>> result = new ArrayList<>();\n        \n        if (root == null) {\n            return result;\n        }\n        \n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            List<Integer> currentLevel = new ArrayList<>();\n\n            for (int i = 0; i < size; i++) {\n                TreeNode currentNode = queue.poll();\n                currentLevel.add(currentNode.val);\n\n                if (currentNode.left != null) {\n                    queue.offer(currentNode.left);\n                }\n                if (currentNode.right != null) {\n                    queue.offer(currentNode.right);\n                }\n            }\n\n            result.add(currentLevel);\n        }\n\n        return result;\n    }\n}\n\n```\n![image.png](https://assets.leetcode.com/users/images/880e765d-0c21-441c-b0c3-6ebd5d3f89a8_1729575116.0965846.png)\n\n\n\n
['Java']