剑指 Offer 32 - III. 从上到下打印二叉树 III（中等，层序遍历）

class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> v;
    if (root == nullptr) return v;
    queue<TreeNode*> q;
    q.push(root);
    int current_level = 1;   //记录当前是第几层
    while (!q.empty()) {
      int current_level_size = q.size();
      v.push_back(vector<int>());
      for (int i = 1; i <= current_level_size; i++) {
        auto node = q.front();
        q.pop();
        v.back().push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
      }
      if (current_level % 2 == 0) reverse(v.back().begin(), v.back().end());  //实现偶数层反转
      current_level++;
    }
    //加一段代码，实现对应层反转   可以把这段代码优化到上面代码中
    //int i = 1;
    //for (auto& ceng : v) {
    //  if (i % 2 == 0) reverse(ceng.begin(), ceng.end());
    //  i++;
    //}
    return v;
  }
};