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]]

confused what "{1,#,2,3}" means?

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

1  / \ 2   3    /   4    \     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

class Solution {public:    vector
      
       
         > zigzagLevelOrder(TreeNode *root) {        // Note: The Solution object is instantiated only once and is reused by each test case.        queue
        
          que;        stack
         
           sta;        int count=1;        int nextCount=0;        int level=0;        if(root==NULL)return vector
          
           
             > (); que.push(root); TreeNode* p; vector
            
             
               > ret; vector
              
                one; while(que.size()!=0){ p=que.front(); que.pop(); if(p->left!=NULL){ que.push(p->left); nextCount++; } if(p->right!=NULL){ que.push(p->right); nextCount++; } count--; if(level%2==0){ one.push_back(p->val); if(count==0){ ret.push_back(one); one.clear(); level++; count=nextCount; nextCount=0; } } else{ sta.push(p->val); if(count==0){ while(sta.size()!=0){ one.push_back(sta.top()); sta.pop(); } ret.push_back(one); one.clear(); level++; count=nextCount; nextCount=0; } } } return ret; }};