/**

• Definition for a binary tree node.

• struct TreeNode {

• int val;

• TreeNode *left;

• TreeNode *right;

• TreeNode() : val(0), left(nullptr), right(nullptr) {}

• TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

• TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

• };
  /
  class Solution {
  public:
  vector<vector> zigzagLevelOrder(TreeNode root) {
  if(root==NULL){
  vector<vector>v;
  return v;
  }
  vector<vector>store;

  deque<TreeNode*>q;
  q.push_back(root);
  int check = 1;
  while(q.size()!=0){
  int n = q.size();
  vectorfake;

     deque<TreeNode*>sample = q;
       for(int i=0; i<n;i++){
          
           if(q.front()->left!=NULL){
               q.push_back(q.front()->left);
           }
            
           if(q.front()->right!=NULL){
               q.push_back(q.front()->right);
           }
           q.pop_front();    
       }
     if(check%2!=0){
         for(int i =0; i<n;i++){
             fake.push_back(sample.front()->val);
             sample.pop_front();
             
         }
     } 
   else{
         for(int i =0; i<n;i++){
             fake.push_back(sample.back()->val);
             sample.pop_back();
             
         }
       
   }
       

  store.push_back(fake);

     check++;    
       
   }
   
   

  return store;

  }
  };