Using two stacks, optimised solution, C++, Commented and Easy to Understand
Intuition\n Describe your first thoughts on how to solve this problem. \nI\'m using two stacks for this problem as it would take lesser time as each node will g
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI\'m using two stacks for this problem as it would take lesser time as each node will go inside the stack once and come out of the stack once. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe will create two stacks, one stack will contain the elements in the level order transversal format i.e. left to right and another will contain in the reverse form. \nFurther explanation is in the code itself.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        vector<vector<int>> res;\n        if(!root)\n            return res;    // if root is empty just return empty vector\n        stack<TreeNode*> s1,s2; // initialise two stacks\n        s1.push(root); // put root inside the first stack\n        vector<int> curr;  // a vector to contain the elements in the current level\n        while(!s1.empty() || !s2.empty()){  // run loop till both of them are empty\n            curr.resize(0);      // keep the size 0 before going and after coming from a stack\n            while(!s1.empty()){    // run a loop till first stack is empty\n                    TreeNode* temp=s1.top();  // create a node with the top ele. of stack1\n                    curr.push_back(temp->val); //push the value in curr vector\n                    s1.pop();     // remove the topmost ele.\n                    if(temp->left)         // if it has left root push inside stack2 \n                        s2.push(temp->left); // *notice left child is entered first if present*\n                    if(temp->right)     // similarly for right child\n                        s2.push(temp->right);\n            }\n            if(s1.empty() && curr.size()>0)  // if curr size > 0 only then push curr vector otherwise an empty array will be pushed which we don\'t want\n                res.push_back(curr); //push one level\n            \n            curr.resize(0); // this is important as we\'ve to resize this vector to 0 for another level now\n            while(!s2.empty()){       // loop runs exactly the same as stack1 loop \n                    TreeNode* temp=s2.top();\n                    curr.push_back(temp->val);\n                    s2.pop();\n                    if(temp->right)  // * only difference is we will push the right child first if present to maintain a zig zag order*\n                        s1.push(temp->right);\n                    if(temp->left)\n                        s1.push(temp->left);\n            }\n            if(s2.empty() && curr.size()>0)\n                res.push_back(curr);  // push this level\n        }\n        return res; // return the result vector\n    }\n};\n```\n\n# Please upvote if you found it helpful.\n
['C++']