C++ (Easy Approach) | Binary Tree Zigzag Level Order Traversal | LeetCode Solution
Intuition\nFor printing zigzag traversal we have to follow level order printing techniques, hence we can use bfs traversal technique for the level order printin
# Intuition\nFor printing zigzag traversal we have to follow level order printing techniques, hence we can use bfs traversal technique for the level order printing which we can implement using queue data structure.\n# Approach\nWe\'ll take queue data structure which stores the TreeNode pointer and at the very first we will pass root to the queue. then for until our queue is non-empty we will take all the elements which are size of queue and add them into our level vector. now for the zigzag part we can take one flag boolean variable to identify whether the current allocation is left to right or it is right to left, and we\'ll remove that node and add left pointer and right pointer of that node. after completing this process we\'ll add this level vector to the resulting vector and switch the flag boolean variable for the zigzag.\n\n# Complexity\n- Time complexity: O(N) (Queue will visit every node)\n\n- Space complexity: O(N) (Queue will visit every node -> O(N) + 2-D Vector -> O(N))\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        vector<vector<int>> ans;\n        if(root == NULL) return ans;\n        bool flag = true;\n        queue<TreeNode*> q;\n        q.push(root);\n        while(!q.empty())\n        {\n            int size = q.size();\n            vector<int> temp(size);\n            for(int i = 0; i < size; i++)\n            {\n                TreeNode* node = q.front();\n                q.pop();\n                int val = node->val;\n                if(flag)\n                {\n                    temp[i] = val;\n                }\n                else\n                {\n                    temp[size - i - 1] = val;\n                }\n                if(node->left) q.push(node->left);\n                if(node->right) q.push(node->right);\n            }\n            ans.push_back(temp);\n            flag = !flag;\n        }\n        return ans;\n    }\n};\n```
['Tree', 'Breadth-First Search', 'Queue', 'C++']