✅C++ || ✅O(N) - 100% fast using LEVEL ORDER TRAVERSAL || Explained using comments✅||
\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nWe will do Level Order Traversal for each level.\nTake a integer and for each incr
\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nWe will do Level Order Traversal for each level.\nTake a integer and for each increasing level we will also increment this integer and also push elements of level in a 1D vector and when this integer is divisible by 2, we will reverse the vector and then push back this vector to the 2D vector. \n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n) for queue and vector\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    {\n        int i=0;\n        vector<vector<int>> v;\n        // <<IF THE ROOT IS null>>\n        if(root==NULL)\n            return v;\n        queue<TreeNode*> q;\n        TreeNode* t=root;\n        // <<PUSH THE ROOT NODE IN THE QUEUE>>\n        q.push(root);\n        while(!q.empty())\n        {\n            // INCREMENT THE INTEGER FOR EVERY LEVEL\n            i++;\n            vector<int> v1;\n            int s=q.size();\n            // <<ITERATING OVER THE CURRENT SIZE OF THE QUEUE>>\n            for(int i=0;i<s;i++)\n            {\n                t=q.front();\n                v1.push_back(t->val);\n                q.pop();\n                if(t->left)q.push(t->left);\n                if(t->right)q.push(t->right);\n            }\n            // <<IF THE INT IS DIVISIBLE BY 2 THEN REVERSE THE 1D VECTOR>>\n            if(i%2==0)\n                reverse(v1.begin(),v1.end());\n            // <<PUSHING 1D VECTOR IN FINAL 2D VECTOR>>\n            v.push_back(v1);\n        }\n        return v;\n    }\n};\n```
['Queue', 'Binary Tree', 'C++']