Zigzag Level Order Traversal of Binary Tree c++
Intuition\nThe intuition behind this code is to traverse a binary tree in a zigzag manner, where each level of the tree is traversed alternately from left to ri
# Intuition\nThe intuition behind this code is to traverse a binary tree in a zigzag manner, where each level of the tree is traversed alternately from left to right and right to left.\n     This zigzag traversal allows us to create a 2D vector where each inner vector represents a level of the tree, and the values within each inner vector are ordered based on the zigzag traversal.\n\n# Approach\nInitialization: \nInitialize an empty 2D vector to store the zigzag level order traversal results. Also, initialize a queue for level order traversal.\n\nLevel Order Traversal with Zigzag Order:\n->Enqueue the root node into the queue.\n->Begin a loop that continues until the queue is empty.\n->Inside the loop, for each level:\nDetermine the number of nodes in the current level.\nInitialize an empty vector to store the values of the nodes in this level.\n->Iterate through all the nodes in the current level:\nDequeue a node from the front of the queue.\nStore its value in the current level\'s vector.\nPush its left and right children (if they exist) for the next level.\n->Push the vector representing the current level into the 2D vector.\n\nZigzag Ordering:\nAfter completing the traversal, go through the 2D vector representing the levels.\nFor every odd-indexed level (0-indexed), reverse the order of elements.\n\nReturn Result: Return the 2D vector containing the zigzag level order traversal results.\n\n\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(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    vector<vector<int>>v;\n    queue<TreeNode*>q;\n\n    if(root==NULL)\n    {\n        return v;\n    }\n    q.push(root);\n    while(!q.empty())\n    {\n        int n=q.size();\n        //inner list to store curr lvl of elements\n        vector<int>in;\n\n        //Doing 2 steps\n        for(int i=1;i<=n;i++)\n        {\n            //remove front after storing it\n            TreeNode* temp=q.front();\n            q.pop();\n            in.push_back(temp->val);\n\n            //add next lvl elements\n            if(temp->left!=NULL)\n            {\n                q.push(temp->left);\n            }\n            if(temp->right!=NULL)\n            {\n                q.push(temp->right);\n            }\n        }\n        v.push_back(in);\n    }\n    for(int i=0;i<v.size();i++)\n    {\n        if(i%2!=0)\n        {\n            reverse(v[i].begin(),v[i].end());\n        }\n    }\n    return v;\n    }\n};\n```
['C++']