Intuitive Solution using Deque with clean code and Visual Representation of the Deque
Approach:\n\n When we have to print in right direction: We take the nodes from the front of the deque and push the children in the back of the deque\n When we h
### Approach:\n\n* **When we have to print in right direction**: We take the nodes from the front of the deque and push the children in the back of the deque\n* **When we have to print in left direction**: We take the nodes from the back of the deque and push the children in the front of the deque in reverse order since we are traversing the current elements in reverse itself.\n\n\n![image](https://assets.leetcode.com/users/images/54da592b-6f25-44ba-9e05-f1e57a870e70_1627041938.234792.png)\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) \n    {        \n        vector<vector<int>> ans;\n        \n        if(!root)\n            return ans;\n        \n        deque<TreeNode*> nodes;\n        \n        bool right = true;\n        \n        TreeNode *levelEnd = new TreeNode(-1);\n        \n        nodes.push_back(root);\n        nodes.push_back(levelEnd);\n        \n        vector<int> currAns;\n        \n        while(nodes.size() > 1)\n        {\n            if(right)\n            {\n                TreeNode *currNode = nodes.front();\n                \n                if(currNode == levelEnd)\n                {\n                    ans.push_back(currAns);\n                    currAns.clear();\n\n                    right = !right;\n                }\n                else\n                {\n                    nodes.pop_front();\n                    \n                    currAns.push_back(currNode->val);\n                    \n                    if(currNode->left)\n                        nodes.push_back(currNode->left);\n                        \n                    if(currNode->right)\n                        nodes.push_back(currNode->right);\n                }\n            }\n            \n            else\n            {\n                TreeNode *currNode = nodes.back();\n                \n                if(currNode == levelEnd)\n                {\n                    ans.push_back(currAns);\n                    currAns.clear();\n\n                    right = !right;\n                }\n                else\n                {\n                    nodes.pop_back();\n                    \n                    currAns.push_back(currNode->val);\n\n                    if(currNode->right)\n                        nodes.push_front(currNode->right);\n                    \n                    if(currNode->left)\n                        nodes.push_front(currNode->left);\n                }\n            }\n        }\n        ans.push_back(currAns);        \n        \n        return ans;\n    }\n};\n```
[]