103. Binary Tree Zigzag Level Order Traversal

一開始還在想要怎麼樣去交互左右子樹, 後來忽然靈機一動, 我就照bfs的方法做就好了, 然後我在間隔每層, 對vector做reverse

class Solution {
public:
  vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
    vector<vector<int>> res;
    queue<TreeNode *> q;
    q.push_back(root);
    bool reverse = false;
    while (!q.empty()) {
      int len = q.size();
      vector<int> cur_layer;
      for(int i = 0; i < len; i++){
        TreeNode * cur = q.front();
        q.pop();
        cur_layer.push_back(cur->val);
        if(cur->left) q.push(cur->left);
        if(cur->right) q.push(cur->right);
      }
      if(reverse){
        reverse(cur_layer.begin(), cur_layer.end());
      }
      res.push_back(cur_layer);
      reverse =!revserse;
    }
    return res;
  }
};