/**
knakul853
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

        vector<vector<int>>ans;
        if( !root ) return ans;

        int alt = 0;

        queue<TreeNode*>q;
        q.push(root);

        while( !q.empty() ){

            int sz = q.size();
            queue<TreeNode*>tempq;
            vector<int>temp;

            for(int i=0;i<sz;i++){
                 TreeNode* node = q.front();
                  q.pop();

                 temp.push_back(node->val);

                    if(node->left)tempq.push(node->left);

                    if(node->right)tempq.push(node->right);

            }

            q = tempq;
            if(alt) {
                reverse(temp.begin(), temp.end());
            }
            ans.push_back(temp);

            alt = alt^1;

        }

        return ans;
    }
};