vector<int> zigzagTreeTraversal(TreeNode<int> *root)
{
vector<int> result; //net ans
if(root==NULL) return result;
bool lefttoright=true;
queue<TreeNode<int>*> q;
q.push(root);
while(!q.empty()){
int size=q.size();
vector<int> ans(size); //for each level ans
for(int i=0;i<size;i++){
TreeNode<int>*front=q.front();
q.pop();
int index= lefttoright?i :size-i-1;
ans[index]=front->data;
if(front->left) q.push(front->left); //later levels
if(front->right) q.push(front->right);
}
lefttoright=!lefttoright;
for(auto i:ans) result.push_back(i);
}
return result;
}