zigzag traversal of a binary tree
#include<bits/stdc++.h>
using namespace std;
int main()
{
//Just reverse the temporary vector containing all nodes at a level
zigzagLevelOrder(root);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > ans;
if(!root) return ans;
vector<int> curr;
queue<TreeNode*> q;
q.push(root);
int x=0;
while(!q.empty())
{
x++;
int i=q.size();
while(i--)
{
TreeNode* temp=q.front();
q.pop();
curr.push_back(temp->val);
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
//Just reverse the temporary vector curr containing all nodes at a level
if(x%2==0) reverse(curr.begin(),curr.end());
ans.push_back(curr);
curr.clear();
}
return ans;
}