[LeetCode][LCR151]彩灯装饰记录 III—

[LeetCode][LCR151]彩灯装饰记录 III——队列

本文主要是介绍[LeetCode][LCR151]彩灯装饰记录 III——队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

LCR 151. 彩灯装饰记录 III

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

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

示例：
输入：root = [8,17,21,18,null,null,6] 输出：[[8],[21,17],[18,6]]
提示：

节点总数 <= 1000

解法

奇数层和偶数层分开考虑，奇数层从左到右记录，偶数层从右到左记录
比如当前层是奇数层，那么从左到右输出当前节点，而从右到左记录当前节点的右子树和左子树
如果当前层是偶数层，则从右到左输出当前节点，从左到右记录当前节点的左子树和右子树
根据彩灯装饰记录 II，可以使用队列进行记录，并且每次都输出队列中同一层的元素而不输出其他层元素（也就是在增加下一层元素之前，先记录下队列中已有的元素个数（也就是当前层的元素个数））
如果当前层是奇数层，在从左到右输出当前节点的同时，需要从右到左地记录当前节点的子节点，子节点应该放在右边，以免在输出当前节点的时候被输出了
如果当前层是偶数层，在从右向左输出当前节点的同时，需要从左到右记录当前节点的子节点，子节点应该放在左边，以免在从右向左输出当前节点时被输出了
按以上的分析，需要使用双端队列来实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> decorateRecord(TreeNode* root) {vector<vector<int>> ans;if(!root) return ans;deque<TreeNode*> dq;dq.push_back(root);int layerNum=0;while(!dq.empty()){++layerNum;vector<int> v;int size=dq.size();for(int i=0; i<size; ++i){if(layerNum%2){//奇数层从左到右v.push_back(dq.front()->val);if(dq.front()->left) dq.push_back(dq.front()->left);if(dq.front()->right) dq.push_back(dq.front()->right);dq.pop_front();}else{v.push_back(dq.back()->val);if(dq.back()->right) dq.push_front(dq.back()->right);if(dq.back()->left) dq.push_front(dq.back()->left);dq.pop_back();}}   ans.push_back(v);     }return ans;}
};