/*
acwing45等价于leetcode 103
思路：反转
奇数层，不变；偶数层，反转
p、q双队列交叉，实现奇数层、偶数层识别
      1
    /   \
   2     3
  / \   / \
 4   5 6   7
 p = {1} ->level {1}
 q = {2, 3} -> level {3, 2}
 p = {4, 5, 6, 7} -> level {4, 5, 6, 7}
 反转发生在放入level中
*/

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        if (!root) return {};

        vector<vector<int>> res;
        vector<int> level;
        queue<TreeNode*> p, q; // p代表奇数层，q代表偶数层
        p.push(root);
        TreeNode *node = nullptr;
        int len = 0;
        while (p.size() || q.size()) {
            if (p.size()) {
                level = {};
                len = p.size();
                while (len --) {
                    node = p.front(); p.pop();
                    level.push_back(node->val);
                    if (node->left) q.push(node->left);
                    if (node->right) q.push(node->right);
                }
                res.push_back(level);
            }
            else if (q.size()) {
                level = {};
                len = q.size();
                while (len --) {
                    node = q.front(); q.pop();
                    level.push_back(node->val);
                    if (node->left) p.push(node->left);
                    if (node->right) p.push(node->right);
                }
                reverse(level.begin(), level.end());
                res.push_back(level);
            }
        }
        return res;
    }
};