Accepted C++ solution using deque
\n\n# Approach\n Describe your approach to solving the problem. \nAfter seeing the test cases, we can see a pattern that when we are at odd level (assuming leve
\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAfter seeing the test cases, we can see a pattern that when we are at odd level (assuming level of root to be 0), we are taking the Node from the front of the deque and pushing the it\'s right and left node at back of the deque. After seeing this , i.e., insertion and deletion from both ends, we can get the intuition of using a deque.\nThe exact opposite would be true for the nodes at even level.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n- Space complexity:\n- O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        if (!root) return {};\n        vector<vector<int>> res;\n        deque<TreeNode*> q;\n        q.push_back(root); // Pushing the root node to the back of the deque\n        int j = 0; // this will help in making the zigzag pattern\n        while (!q.empty()) {\n            int n = q.size();\n            vector<int> temp;\n            for (int i = 0; i < n; i++) {\n                TreeNode* node;\n                if (j & 1) {\n                    node = q.front();\n                    q.pop_front();\n                } else {\n                    node = q.back();\n                    q.pop_back();\n                }\n                temp.push_back(node->val);\n                if (j & 1) {\n                    if (node->right) {\n                        q.push_back(node->right); // Pushing right child to the back of the deque\n                    }\n                    if (node->left) {\n                        q.push_back(node->left); // Pushing left child to the back of the deque\n                    }\n                } else {\n                    if (node->left) {\n                        q.push_front(node->left); // Pushing left child to the front of the deque\n                    }\n                    if (node->right) {\n                        q.push_front(node->right); // Pushing right child to the front of the deque\n                    }\n                }\n            }\n            j++;\n            res.push_back(temp);\n        }\n        return res;\n    }\n};\n```
['C++']