Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

&nbsp;
Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]


Example 2:

Input: root = [1]
Output: [[1]]


Example 3:

Input: root = []
Output: []


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [0, 2000].
	-100 &lt;= Node.val &lt;= 100


class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        
        ans = []
        
        node = root 
        
        q = collections.deque([node])
        
        order = -1 
        
        while q:
            order = -order
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                
                level.append(node.val)
                
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                    
            ans.append(level[::order])
                
        return ans
/**
 * 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) {
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        List<List<Integer>> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        q.offer(root);
        boolean flag=true;
        while(!q.isEmpty()){
            int size=q.size();
            List<Integer> curr=new ArrayList<>();
            for(int i=0;i<size;i++){
                if(q.peek().left!=null){
                    q.offer(q.peek().left);
                }
                if(q.peek().right!=null){
                    q.offer(q.peek().right);
                }
                if(flag==true){
                    curr.add(q.poll().val);
                }else{
                    curr.add(0,q.poll().val);
                }
            }
            if(flag==true){
                flag=false;
            }else{
                flag=true;
            }
            res.add(curr);
        }
        return res;
    }
}
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if(!root) return ans;
    vector<int> r;
    queue<TreeNode*> q;
    int count=1;
    q.push(root);
    q.push(NULL);
    while(1){
        if(q.front()==NULL){
            q.pop();
            if(count%2==0) reverse(r.begin(),r.end());
            ans.push_back(r);
            if (q.empty()) return ans;
            q.push(NULL);
            r.resize(0);
            count++;
            continue;
        }
        
            r.push_back((q.front())->val);
            if(q.front()->left)q.push((q.front())->left); 
            if(q.front()->right)q.push((q.front())->right);
            
            q.pop();
    }
    return ans;

    }
};
var zigzagLevelOrder = function(root) {
    let result = []
    if(root == null) return result
    
    let queue = []
    let leftToRight = true
    
    queue.push(root)
    
    while(queue.length != 0) {
        let qSize = queue.length
        let ans = []
        
        // Processing level
        for(let i=0;i<qSize;i++) {
            let front = queue.shift()
            
            let index = leftToRight ? i : qSize-i-1
            ans[index] = front.val
            
            if(front.left) queue.push(front.left)
            if(front.right) queue.push(front.right)
        }
        // changing order of operation
        leftToRight = !leftToRight
        
        result.push(ans)
    }
    
    return result
};
Binary Tree Zigzag Level Order Traversal