给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

3   / \  9  20    /  \   15   7

返回锯齿形层次遍历如下：

[  [3],  [20,9],  [15,7]]

首先我们想一下二叉树的层序遍历的思想：

层序遍历的主要思路就是先把根节点存入，然后输出，输出的同时把根节点的左右孩子存入，再把左孩子输出，同样输出的同时把左孩子的孩子在存入，直到遍历完成，例如：

      a

  b       c

d   e   f   g   

先把a存入，然后输出a，输出a的同时把b c存入，然后再输出b,输出b的同时存入d e，继续输出c，然后存入f g，直到全部输出

//层序遍历vector
     
       levelOrder(TreeNode *root) {	vector
      
        answer;	queue
       
        p;	if (root == nullptr) return answer;	p.push(root);	TreeNode* h = nullptr;	while (!p.empty()) {		int size = p.size();		while (size--) {			h = p.front();			answer.push_back(h->val);			p.pop();			//子树非空，则压入队列   			if (h->left != NULL)				p.push(h->left);			if (h->right != NULL)				p.push(h->right);		}	}	return answer;}
       
      
     

思路一：对特定输入的结果进行反转输出

因为输出结果是第二层、第四层、第六层。。。的层序遍历结果反向输出，可以在输出时将对应的行反转输出即可。

//蛇形遍历(反转)vector
     
      
       > zigzagLevelOrder(TreeNode* root) {	vector
       
        
         > answer;	if (root == nullptr) return answer;	queue
         
          p;	p.push(root);	TreeNode* h = nullptr;	while (!p.empty()) {		int size = p.size();		vector
          
            temp; while (size--) { h = p.front(); temp.push_back(h->val); p.pop(); //子树非空，则压入队列 if (h->left != NULL) p.push(h->left); if (h->right != NULL) p.push(h->right); } answer.push_back(temp); } for (int i = 1; i < answer.size(); i += 2) { reverse(answer[i].begin(), answer[i].end()); } return answer;}
          
         
        
       
      
     

思路二：利用双端队列

//蛇形遍历（双端队列）vector
     
      
       > zigzagLevelOrder(TreeNode* root) {	vector
       
        
         > answer;	if (root == nullptr) return answer;	deque
         
           deq;	deq.push_back(root);	int flag = 0;	int size = 1;	TreeNode *node = nullptr;	while (!deq.empty()) {		vector
          
            vec; size = deq.size(); for (int i = 0; i < size; i++) { node = deq.front(); deq.pop_front(); //从左到右 if (flag % 2 == 0) { vec.push_back(node->val); } else { vec.insert(vec.begin(), node->val); } if (node->left != NULL) deq.push_back(node->left); if (node->right != NULL) deq.push_back(node->right); } answer.push_back(vec); flag++; } return answer;}
          
         
        
       
      
     

研究了一下双端队列，后来发现改成队列就可以了。

class Solution {public:    vector
     
      
       > zigzagLevelOrder(TreeNode* root) {      vector
       
        
         > answer;      if (root == nullptr) return answer;        queue
         
           deq;      deq.push(root);      int flag = 0;      int size = 1;      TreeNode *node = nullptr;        while (!deq.empty()) {          vector
          
            vec; size = deq.size(); for (int i = 0; i < size; i++) { node = deq.front(); deq.pop(); //从左到右 if (flag % 2 == 0) { vec.push_back(node->val); } else { vec.insert(vec.begin(), node->val); } if (node->left != NULL) deq.push(node->left); if (node->right != NULL) deq.push(node->right); } answer.push_back(vec); flag++; } return answer; } };