本题也属于层次遍历的变形，不同之处在于其遍历的方法是交替进行的，形成一个ZigZag的曲线形式，如下：

代码如下：

1 struct TreeNode { 2     int            val; 3     TreeNode*    left; 4     TreeNode*    right; 5     TreeNode(int x): val(x), left(NULL),right(NULL) {} 6 }; 7  8 void Swap(vector
     
       &ivec) 9 {10     int temp = 0;11     int len = ivec.size();12     for (int i = 0; i < len/2; i ++) {13         temp = ivec.at(i);14         ivec.at(i) = ivec.at(len-1-i);15         ivec.at(len-1-i) = temp;16     }17 }18 19 vector
      
       
         > zigzagLevelOrder(TreeNode *root)20 {21     vector
        
         
           > tree_vector;22     vector
          
            ivec;23 queue
           
             tree_queue;24 if (NULL == root)25 return tree_vector;26 27 tree_queue.push(root);28 tree_queue.push(NULL);29 int nLevelCount = 1;30 while (true) {31 TreeNode *pTemp = tree_queue.front();32 tree_queue.pop();33 if (pTemp == NULL) {34 if (nLevelCount%2 == 0) { //if the num of level is odd, swap the ivec;35 Swap(ivec);36 }37 tree_vector.push_back(ivec);38 ivec.clear();39 if (tree_queue.empty())40 break;41 tree_queue.push(NULL);42 nLevelCount ++;43 }44 else {45 ivec.push_back(pTemp->val);46 if (pTemp->left)47 tree_queue.push(pTemp->left);48 if (pTemp->right)49 tree_queue.push(pTemp->right);50 }51 }52 return tree_vector;53 }