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 class Solution { 2 public: 3     void reverse(vector
     
       &arr) { 4         for (int i = 0, j = arr.size() - 1; i < j; i++, j--) swap(arr[i], arr[j]); 5     } 6      7     vector
      
       
         > zigzagLevelOrder(TreeNode *root) { 8         vector
        
         
           > ans; 9         if (root == NULL) return ans;10         vector
          
           
             > layers(2);11 vector
            
              tmp;12 int cur = 0, next = 1;13 layers[cur].push_back(root);14 15 while (!layers[cur].empty()) {16 layers[next].clear();17 tmp.clear();18 for (auto node : layers[cur]) {19 if (node->left) layers[next].push_back(node->left);20 if (node->right) layers[next].push_back(node->right);21 tmp.push_back(node->val);22 }23 if (cur == 1) reverse(tmp);24 ans.push_back(tmp);25 cur = !cur, next = !next;26 }27 28 return ans;29 }30 };