Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3   /   9  20    /     15   7

return its zigzag level order traversal as:

[  [3],  [20,9],  [15,7]]

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector<vector<int> > zigzagLevelOrder(TreeNode *root) {13        14         vector<vector<int> > result;15         queue<TreeNode*> q;16        17         if(root==NULL) return result;18         q.push(root);19        20         int numNode=1;21        22         bool isOdd=true;23        24         while(!q.empty())25         {26             vector<int> cur;27             int nextLevelCount=0;28             for(int i=0;i<numNode;i++)29             {30                 TreeNode *node=q.front();31                 cur.push_back(node->val);32                 q.pop();33                 if(node->left!=NULL)34                 {35                     q.push(node->left);36                     nextLevelCount++;37                 }38                39                 if(node->right!=NULL)40                 {41                     q.push(node->right);42                     nextLevelCount++;43                 }44             }45            46             if(isOdd)47             {48                 result.push_back(cur);49             }50             else51             {52                 reverse(cur.begin(),cur.end());53                 result.push_back(cur);54             }55            56             isOdd=!isOdd;57            58             numNode=nextLevelCount;59         }60        61         return result;62        63     }64 };