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;
    }
};