class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> ans; queue<TreeNode*> dq; if(root)dq.push(root); int flag = 0; while(!dq.empty()){ vector<int> curlvl; int size = dq.size(); // traverse all the nodes of current level for(int s=0; s<size; s++){ root = dq.front(); dq.pop(); if(flag) curlvl.insert(curlvl.begin(), root->val); else curlvl.push_back(root->val); if(root->left) dq.push(root->left); if(root->right) dq.push(root->right); } flag^=1; ans.push_back(curlvl); } return ans; } };