給定一個二叉樹，返回其節點值的鋸齒形層次遍歷。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。

例如：
給定二叉樹?[3,9,20,null,null,15,7],

    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<int> levelOrder(TreeNode *root) {vector<int> answer;queue<TreeNode *>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<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> answer;if (root == nullptr) return answer;queue<TreeNode *>p;p.push(root);TreeNode* h = nullptr;while (!p.empty()) {int size = p.size();vector<int> 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<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> answer;if (root == nullptr) return answer;deque<TreeNode*> deq;deq.push_back(root);int flag = 0;int size = 1;TreeNode *node = nullptr;while (!deq.empty()) {vector<int> 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<vector<int>> zigzagLevelOrder(TreeNode* root) {  vector<vector<int>> answer;  if (root == nullptr) return answer;  queue<TreeNode*> deq;  deq.push(root);  int flag = 0;  int size = 1;  TreeNode *node = nullptr;  while (!deq.empty()) {  vector<int> 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;  
}  
};