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   7return its zigzag level order traversal as:[  [3],  [20,9],  [15,7]]

　　和level order traversal 唯一的不同是，偶数行逆序输出，逆序可是使用stack来实现。其他的实现和level order实现大同小异

 

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
      
        > zigzagLevelOrder(TreeNode *root) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        vector
       
        
         > result ;        if(root ==NULL) return result;        std::queue
         
           q,p;        std::stack
          
            kit; vector
           
             mResult; bool f = false ; q.push(root); while(!q.empty()){ mResult.clear(); if(f) { while(!q.empty()){ root = q.front(); q.pop(); kit.push(root->val); if(root->left) p.push(root->left); if(root->right) p.push(root->right); } while(!kit.empty()) { mResult.push_back(kit.top()); kit.pop(); } f = false; }else{ while(!q.empty()){ root = q.front(); q.pop(); mResult.push_back(root->val); if(root->left) p.push(root->left); if(root->right) p.push(root->right); } f = true ; } result.push_back(mResult); while(!p.empty()){ q.push(p.front()); p.pop(); } } return result; }};