一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照如下规则记录彩灯装饰结果：

第一层按照从左到右的顺序记录

除第一层外每一层的记录顺序均与上一层相反。即第一层为从左到右，第二层为从右到左。

示例 1：

**输入：**root = [8,17,21,18,null,null,6]
输出：[[8],[21,17],[18,6]]

提示：

节点总数 <= 1000

同层序遍历，每层要输出的元素是提前能知道的，所以我们可以根据标志位直接找到当前元素应该放在哪个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode *root) {
        vector<vector<int>> ans;
        queue<TreeNode *> que;
        if (root != nullptr)
            que.push(root);
        bool flag = true;
        while (!que.empty()) {
            int len = que.size();
            vector<int> mid(len);
            for (int i = len; i > 0; i--) {
                TreeNode *cur = que.front();
                if (cur->left != nullptr)
                    que.push(cur->left);
                if (cur->right != nullptr)
                    que.push(cur->right);
                que.pop();
                if (flag)
                    mid[len - i] = cur->val;
                else if (!flag)
                    mid[i - 1] = cur->val;
            }
            flag = !flag;
            ans.push_back(mid);
        }
        return ans;
    }
};

也可以使用两个双端队列交替存储，用两个是因为每次入队元素会影响出队元素的遍历

写完后发现只用到了push/ppo front，所以用两个栈存储也可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode *root) {
        vector<vector<int>> ans;
        deque<TreeNode *> que, rque;
        if (root != nullptr)
            que.push_front(root);
        bool flag = true;
        while (!que.empty() || !rque.empty()) {
            vector<int> mid;
            int i = que.empty() ? rque.size() : que.size();
            for (i; i > 0; i--) {
                if (flag) {
                    TreeNode *cur = que.front();
                    if (cur->left != nullptr)
                        rque.push_front(cur->left);
                    if (cur->right != nullptr)
                        rque.push_front(cur->right);
                    que.pop_front();
                    mid.push_back(cur->val);
                } else if (!flag) {
                    TreeNode *cur = rque.front();
                    if (cur->right != nullptr)
                        que.push_front(cur->right);
                    if (cur->left != nullptr)
                        que.push_front(cur->left);
                    rque.pop_front();
                    mid.push_back(cur->val);
                }
            }
            flag = !flag;
            ans.push_back(mid);
        }
        return ans;
    }
};