Binary Tree Zigzag Level Order Traversal in Java Simple Code
\n# Approach\n Describe your approach to solving the problem. \n\n- Create an empty list to store the final result.\n- If the root of the tree is null, return t
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n- Create an empty list to store the final result.\n- If the root of the tree is null, return the empty list.\n- Create a queue to store the nodes of each level of the tree.\n- Add the root node to the queue.\n- Create a temporary node variable and a boolean variable to indicate the zigzag order.\n- Create an empty sublist to store the values of each level.\n- While the queue is not empty, do the following:\n  - Get the size of the queue, which is the number of nodes in the current level.\n  - For each node in the current level, do the following:\n    - Remove the node from the queue and assign it to the temporary node variable.\n    - Add its value to the sublist.\n    - If it has a left child, add it to the queue.\n    - If it has a right child, add it to the queue.\n  - If the zigzag order is false, reverse the sublist.\n  - Add the sublist to the final result list.\n  - Toggle the zigzag order variable.\n- Return the final result list.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\no(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\no(n)\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> list = new ArrayList<>();\n        if(root == null){\n            return list;\n        }\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.add(root);\n        TreeNode temp = null;\n        Boolean zigZag = true;\n        List<Integer> subList;\n        while(!queue.isEmpty()){\n            int size = queue.size();\n            subList = new ArrayList<>();\n            for(int i = 0; i<size; i++){\n                temp = queue.remove();\n                subList.add(temp.val);\n                if(temp.left != null){\n                   queue.add(temp.left);\n                }\n                if(temp.right != null){\n                   queue.add(temp.right);\n                }\n            }\n            if(zigZag == false){\n                Collections.reverse(subList);\n            }\n            list.add(subList);\n            zigZag = !zigZag;\n        }\n        return list;\n    }\n}\n```
['Java']