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]

]

class Solution {public:    vector
     
      
        > levelOrder(TreeNode *root) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        vector
       
        
          > ans;        vector
         
           layer_v;        if (!root){            return ans;        }                int layer = 0;        queue
          
           
             > qu; qu.push(make_pair(root,0)); pair
            
              node; while(!qu.empty()){ node = qu.front(); qu.pop(); if (node.second == layer){ layer_v.push_back(node.first->val); }else{ ans.push_back(layer_v); layer++; layer_v.clear(); layer_v.push_back(node.first->val); } if (node.first->left){ qu.push(make_pair(node.first->left,node.second+1)); } if (node.first->right){ qu.push(make_pair(node.first->right,node.second+1)); } } ans.push_back(layer_v); return ans; }};