ZigZag Traversal | No Reverse | Deque | 1 ms
IntuitionThe interviewer might be interested in actual zig zag traversal and may not care about reversing the level's elements based on level parity. We can sim
# Intuition
The interviewer might be interested in actual zig zag traversal and may not care about reversing the level's elements based on level parity. We can simulate actual level order traversal by using a deque.
# Approach
Based on level parity, we can add elements to either at the front of the deque or at the end. 

For even levels (left to right traversal):

1. Remove nodes from the front (pollFirst()).
2. Add child nodes from left to right (offerLast()).

For odd levels (right to left traversal):
1. Remove nodes from the back (pollLast()).
2. Add child nodes from right to left (offerFirst()).

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O(n), n = number of nodes in the tree.
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    O(n), n = number of nodes in the tree.


# Code
```java []
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null)return new ArrayList<>();
        ArrayDeque<TreeNode> dq = new ArrayDeque<>();
        dq.offer(root);
        List<List<Integer>> result = new ArrayList<>();
        boolean leftToRight = true;

        while(!dq.isEmpty()){
            List<Integer> currLevel = new ArrayList<>();
            for(int i = dq.size(); i > 0; i--){
                TreeNode curr = (leftToRight)?dq.pollFirst():dq.pollLast();
                currLevel.add(curr.val); 
                if(leftToRight){
                    if(curr.left != null)
                        dq.offerLast(curr.left);
                    if(curr.right != null)
                        dq.offerLast(curr.right);
                }   
                else{
                    if(curr.right != null)
                        dq.offerFirst(curr.right);
                    if(curr.left != null)
                        dq.offerFirst(curr.left);
                }
            }
            
            leftToRight = !leftToRight;
            result.add(currLevel);
        }
        return result;
    }
}       
```
['Java']