Two stack approach (c++ solution)
This can be solve using two stack current and next.\n\n\nclass Solution {\npublic:\n    \n    void solve(TreeNode* root,vector<vector<int>> &ans){\n        if(r
This can be solve using two stack current and next.\n\n```\nclass Solution {\npublic:\n    \n    void solve(TreeNode* root,vector<vector<int>> &ans){\n        if(root==NULL) return ;\n        \n        stack<TreeNode*> curr;\n        stack<TreeNode*> next;\n        \n        bool leftToRight=true;\n        \n\t\t//push  root to the curr\n        curr.push(root);\n         vector<int> v;\n        while(!curr.empty()){\n            TreeNode* node=curr.top();\n            curr.pop();\n            if(node){\n                v.push_back(node->val);\n\t\t\t\t\n\t\t\t\t//add data in the next according to the order (leftToRight)\n                if(leftToRight){\n                    if(node->left){\n                        next.push(node->left);\n                    }\n                    if(node->right){\n                        next.push(node->right);\n                    }\n                }\n                else{\n                    if(node->right){\n                        next.push(node->right);\n                    }\n                    if(node->left){\n                        next.push(node->left);\n                    }\n                }\n            }\n            \n            if(curr.empty()){\n                ans.push_back(v);\n                leftToRight=!leftToRight;\n                swap(curr,next);\n                v.clear();\n            }\n        }\n    }\n    \n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        vector<vector<int>> ans;\n        solve(root,ans);\n        return ans;\n    }\n};\n```\n\n\n**Time complexity:** **O(n)** (We are traversing through all nodes once )\n**Space complexity:** **O(n) + O(n)** (For two stacks curr and next)
['Stack', 'C++']