Clear iterative solution with deque, no reverse
for zig, pop_back, push_front, left then right, \n\n for zag, pop_front, push_back, right then left\n\n    vector> zigzagLevelOrder(TreeNode* root) {\n        v
 for zig, pop_back, push_front, left then right, \n\n for zag, pop_front, push_back, right then left\n\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        vector<vector<int>> res;\n        if(!root) return res;\n        std::deque<TreeNode*> deq;\n        deq.push_back(root);\n        int iszig=1;\n        while(!deq.empty()) {\n            int sz=deq.size();\n            iszig=iszig^1;\n            vector<int> row;\n            while(sz--) {\n                if(iszig) { // pop_front, push_back, right then left\n                    root=deq.front();deq.pop_front();\n                    row.push_back(root->val);\n                    if(root->right) deq.push_back(root->right);\n                    if(root->left) deq.push_back(root->left);\n                }\n                else { // pop_back, push_front, left then right\n                    root=deq.back();deq.pop_back();\n                    row.push_back(root->val);\n                    if(root->left) deq.push_front(root->left);\n                    if(root->right) deq.push_front(root->right);\n                }\n            }\n            res.push_back(row);\n        }\n        return res;\n    }
[]