[C++] 3 Methods ||2queue->1queue||
\n\n# Method-1 -> By 2 Stacks\n\n\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        if(root==NULL)return {};\n    
\n\n# Method-1 -> By 2 Stacks\n```\n\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        if(root==NULL)return {};\n        stack<TreeNode*>st1,st2;\n        st1.push(root);\n        vector<vector<int>>res;\n        while(!st1.empty()){\n            vector<int>t;\n            while(!st1.empty()){\n                 TreeNode*p=st1.top();\n                 st1.pop();\n                  t.push_back(p->val);\n                  if(p->left)st2.push(p->left);\n                  if(p->right)st2.push(p->right);\n            }\n            if(t.size()) res.push_back(t);\n            t={};\n            while(!st2.empty()){\n                 TreeNode*p=st2.top();\n                 st2.pop();\n                  t.push_back(p->val);\n                  if(p->right)st1.push(p->right);\n                  if(p->left)st1.push(p->left);\n            }\n            if(t.size()) res.push_back(t);\n        }\n        return res;\n    }\n};\n```\n# Method-2 ->By 2queue\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n    if(!root) return {};\n    queue<TreeNode*>q1; //this will use for even levels\n    queue<TreeNode*>q2; //this will use for odd levels\n    q1.push(root);\n    q2.push(root);\n    int lvl=0;\n    vector<vector<int>>res;\n    while(!q1.empty()){\n       int size=q1.size();\n       vector<int>tmp;\n       for(int i=0;i<size;i++){\n        TreeNode*front1=q1.front();\n        TreeNode*front2=q2.front();\n        q1.pop();\n        q2.pop();\n        if(lvl%2==0) tmp.push_back(front1->val);       \n        \n        else tmp.push_back(front2->val);\n        \n        \n        if(front1->left)q1.push(front1->left);\n        if(front1->right)q1.push(front1->right);\n         //second queue is for odd levels so first we insert right child then left   \n        if(front2->right)q2.push(front2->right);\n        if(front2->left)q2.push(front2->left);\n            \n       }\n       res.push_back(tmp);\n          lvl++;\n    }\n    return res;\n    }\n};\n```\n# Method-3 By 1 queue\n```\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        if(root==NULL)return {};\n        //optimised one by one queue\n        queue<TreeNode*>q;\n        q.push(root);\n        vector<vector<int>>res;\n        bool islefttoright=true;\n        while(!q.empty()){\n            int s=q.size();\n            vector<int>t;\n            for(int i=0;i<s;i++){\n                  TreeNode*front=q.front();\n                  q.pop();\n                 t.push_back(front->val);\n                  if(front->left)q.push(front->left);\n                  if(front->right)q.push(front->right);\n            }\n            if(!islefttoright){\n                 reverse(t.begin(),t.end());\n            }\n            res.push_back(t);\n            islefttoright=!islefttoright;\n          \n        }\n\n        return res;\n    }\n};\n```
['Stack', 'Queue', 'C++']