Two simple approaches : O(n)
1.)Recursion: After doing level order traversal using recursion, we simply reverse the vectors at alternate levels\n\nclass Solution {\npublic:\n    void helper
**1.)Recursion:** After doing level order traversal using recursion, we simply reverse the vectors at alternate levels\n```\nclass Solution {\npublic:\n    void helper(TreeNode*root,vector<vector<int>>&res,int level)\n    {\n        if(!root) return;   \n        if(level>=res.size())\n            res.push_back({});\n        res[level].push_back(root->val);\n        helper(root->left,res,level+1);\n        helper(root->right,res,level+1);\n    }\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        vector<vector<int>>res;\n        if(!root)   return res;\n        helper(root,res,0); \n        for(int i=1;i<res.size();i=i+2)\n        {\n            reverse(res[i].begin(),res[i].end());\n        }\n        return res;\n    }\n};\n```\n*Runtime:0ms\nSpace: O(n) for res vector\nTime:O(n)*\n\n**2.)Using queue(BFS):**\n```\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        vector<vector<int>>res;\n        if(!root)   return res;\n        vector<int>row;\n        queue<TreeNode*>q;\n        int x=0;\n        q.push(root);\n        while(!q.empty())\n        {\n            int size=q.size();\n            for(int i=0;i<size;i++)\n            {\n                TreeNode*root=q.front();\n                q.pop();\n                row.push_back(root->val);\n                if(root->left!=NULL)\n                    q.push(root->left);\n                if(root->right!=NULL)\n                    q.push(root->right);\n            }\n            if(x%2==0)\n                res.push_back(row);\n            else\n            {\n                reverse(row.begin(),row.end());\n                res.push_back(row);\n            }\n            row.clear();\n            x+=1;\n        }\n        return res;\n    }\n};\n```\n*Runtime:0ms\nSpace:O(n)\nTime:O(n)*\n\nI hope this helped!!\nIf you like, please **UPVOTE**\'\nHappy Coding :)
['Stack', 'Depth-First Search', 'Breadth-First Search', 'Recursion', 'Queue', 'C', 'C++']