/**
方法一：层次遍历模版
加一个flag判断是否要把该层结果逆序
*/
class Solution {
public List<List<Integer>> decorateRecord(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
Deque<TreeNode> q = new ArrayDeque<>();
List<List<Integer>> res = new ArrayList<>();
q.add(root);
int flag = 0;
while (q.size() > 0){
List<Integer> oneRes = new ArrayList<>();
int sz = q.size();
for (int i = 0; i < sz; i++){
TreeNode node = q.pop();
oneRes.add(node.val);
if (node.left != null){
q.add(node.left);
}
if (node.right != null){
q.add(node.right);
}
}
if (flag == 1){
List<Integer> oneResNew = new ArrayList<>();
for (int i = oneRes.size() - 1; i >= 0; i--){
oneResNew.add(oneRes.get(i));
}
oneRes = oneResNew;
}
flag = (flag + 1) % 2;
res.add(oneRes);
}
return res;
}
}
class Solution {
public List<List<Integer>> decorateRecord(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null)
return res;
Queue<TreeNode> q = new LinkedList<>();
boolean reverse = false;
q.add(root);
while (!q.isEmpty()) {
int n = q.size();
List<Integer> sub = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode temp = q.poll();
// 取的同时，有左加左，有右加右
sub.add(temp.val);
if (temp.left != null)
q.add(temp.left);
if (temp.right != null)
q.add(temp.right);
}
if (reverse) {
Collections.reverse(sub);
}
res.add(sub);
reverse = !reverse;
}
return res;
}
}
class Solution {
public List<List<Integer>> decorateRecord(TreeNode root) {
Queue<TreeNode> tree = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
if (root != null)
tree.offer(root);
int ceng = 1;
while (!tree.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
int n = tree.size();
if (ceng % 2 == 0) {
Stack<Integer> t = new Stack<>();
for (int i = 0; i < n; i++) {
TreeNode node = tree.poll();
t.push(node.val);
if (node.left != null)
tree.offer(node.left);
if (node.right != null)
tree.offer(node.right);
}
while(!t.empty()){
tmp.add(t.pop());
}
} else {
for (int i = 0; i < n; i++) {
TreeNode node = tree.poll();
tmp.add(node.val);
if (node.left != null)
tree.offer(node.left);
if (node.right != null)
tree.offer(node.right);
}
}
ans.add(tmp);
ceng++;
System.out.print(ceng);
}
return ans;
}
}
shuaidi
共以下 20 个回答
LCR 151. 彩灯装饰记录 III
时间O(N)，空间O(N)
//加了一个标志位判断是否把容器反转> decorateRecord(TreeNode* root) {> result; temp; cur = node.front();
class Solution {
public:
vector<vector
queue<TreeNode> node;
vector<vector
if (root != nullptr) {
node.push(root);
}
bool ltor = true;
while (!node.empty()) {
vector
int size = node.size();
bool targ = false;
for (int i = 0; i < size; ++i) {
TreeNode
node.pop();
temp.push_back(cur->val);
};
题解
在上面一题的基础上，需要逆向数据的时候，其实不需要逆向遍历，正向遍历，通过list的addFirst逆向存储即可。
方法 和第二版本类似 但是添加一个指示器来确认是否要翻转存下来的list.
time O(n) space O(n)
加入数组反转操作
时间复杂度O(n), 空间复杂度O(n)
当层数为偶数的时候就反转集合，或者存入栈再取出
On On
打卡
思路：相对于上一题再加上一个flag,每层队列循环完之后取反
根据flag的值来确认是从队头插入还是队尾
时间o(n)空间o(n)
时间复杂度O(N)，空间复杂度O(N)。
//在第二题的基础上加一个锁，为true就是从左到右，false为从右到左> decorateRecord(TreeNode root) { queue = new LinkedList<>();> result = new ArrayList<>(); tmp = new ArrayList<>();
class Solution {
public List<List
Queue
List<List
if (root != null) queue.add(root);
boolean lock = true;
while(!queue.isEmpty()) {
List
for (int i = queue.size(); i > 0; i–) {
TreeNode tmpNode = queue.poll();
tmp.add(tmpNode.val);
if (tmpNode.left!=null) queue.add(tmpNode.left);
if (tmpNode.right!=null) queue.add(tmpNode.right);
}
if (lock) {
result.add(tmp);
lock = !lock;
} else {
result.add(tmp.reversed());
lock = !lock;
}
}
定义一个变量reverse，为true就反转
class Solution {> decorateRecord(TreeNode root) { > res = new ArrayList(); deque = new ArrayDeque(); list = new ArrayList(); 0) Collections.reverse(list);
public List<List
List<List
if(root null) return res;
Deque
deque.offer(root);
int depth = 0;
while(!deque.isEmpty()){
int size = deque.size();
List
while(size– > 0){
TreeNode cur = deque.poll();
list.add(cur.val);
if(cur.left != null){
deque.offer(cur.left);
}
if(cur.right != null){
deque.offer(cur.right);
}
}
if(++depth % 2
res.add(list);
}
return res;
}
}
层次遍历，记录深度，偶数则将结果reverse
时间：O（n）
空间：O（n）
当层数为偶数时用栈存储然后再导入,相当于反过来
时间复杂度O(n)
空间复杂度O(n)
看了题解可以知道用双端队列
思路：层序遍历，奇数层不需要反转当前层的节点，偶数层需要反转当前层的节点。
时间复杂度：O(n)。
空间复杂度：O(n)。