给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行） 

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出一棵二叉树 {3,9,20,#,#,15,7},

3   / \  9  20    /  \   15   7

返回其锯齿形的层次遍历为：

[  [3],  [20,9],  [15,7]] 思路：其实还是层次遍历的思想借助于辅助队列，在这里因为某些层需要逆序输出，所以设置一个标记位，并调用       容器的reverse()函数，将需要逆序的层逆序，这样就能得到锯齿形的层次遍历结果了。

/** * Definition of TreeNode: * class TreeNode { * public: *     int val; *     TreeNode *left, *right; *     TreeNode(int val) { *         this->val = val; *         this->left = this->right = NULL; *     } * } */ class Solution {    /**     * @param root: The root of binary tree.     * @return: A list of lists of integer include      *          the zigzag level order traversal of its nodes' values      */         /*    思路：其实还是层次遍历的思想，在这里因为某些层需要逆序输出，所以设置一个标记位，并调用容器的reverse()函数，将          需要逆序的层逆序，这样就能得到锯齿形的层次遍历结果了。    */public:    vector
       
        
         > zigzagLevelOrder(TreeNode *root) {        // write your code here        vector
         
          
           > vec;        if(root==NULL){            return vec;        }                bool cur=false;              queue
           
             que;          que.push(root);                  while(!que.empty()){            int count=que.size();            vector
            
              vec_temp; while(count--){ TreeNode *temp=que.front(); que.pop(); vec_temp.push_back(temp->val); if(temp->left){ que.push(temp->left); } if(temp->right){ que.push(temp->right); } } if(cur){ reverse(vec_temp.begin(),vec_temp.end()); } cur=!cur; vec.push_back(vec_temp); } return vec; }};