# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque #
class Solution:
def decorateRecord(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
queue=collections.deque() #
res=[]
queue.append(root)
while queue:
for _ in range(len(queue)):
cur=queue.popleft()
res.append(cur.val) #放在这里添加res
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return res
/**
方法一：层次遍历模版，时间复杂度O(N), 空间复杂度O(N)
*/
class Solution {
public int[] decorateRecord(TreeNode root) {
if (root == null){
return new int[]{};
}
Deque<TreeNode> q = new ArrayDeque<>();
List<Integer> res = new ArrayList<>();
q.add(root);
while (q.size() > 0){
TreeNode node = q.pop();
res.add(node.val);
if (node.left != null){
q.add(node.left);
}
if (node.right != null){
q.add(node.right);
}
}
int[] ans = new int[res.size()];
for ( int i = 0; i < res.size(); i++){
ans[i] = res.get(i);
}
return ans;
}
}
//需要一个辅助队列，每次弹出一个节点，输出他的值，并把他的左右孩子压入队列，直到队列为空
class Solution {
public int[] decorateRecord(TreeNode root) {
Queue queue = new LinkedList<>();
List arr = new ArrayList();
int n = 0;
if (root == null) {
int [] zeroArr = new int [0];
return zeroArr;
}else {
queue.offer(root);
}
while (!queue.isEmpty()) {
n++;
TreeNode temp = queue.poll();
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
arr.add(temp.val);
}
// int[] result = arr.stream().mapToInt(Integer::intValue).toArray();
int [] result = new int [n];
int i = 0;
for (int j : arr) {
result[i] = j;
i++;
}
class Solution {
public int[] decorateRecord(TreeNode root) {
if(root == null)return new int[0];
Queue<TreeNode> tree = new LinkedList<>();
ArrayList<Integer> ans = new ArrayList<>();
tree.offer(root);
while(!tree.isEmpty()){
if(tree.peek().left!=null)
tree.offer(tree.peek().left);
if(tree.peek().right!=null)
tree.offer(tree.peek().right);
ans.add(tree.poll().val);
}
int[] res = new int[ans.size()];
for(int i = 0;i<ans.size();i++){
res[i] = ans.get(i);
}
return res;
}
}
class Solution {
public int[] decorateRecord(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
list.add(root);
int index = 0;
TreeNode current = list.get(index);
while(current != null){
if(current.left != null){
list.add(current.left);
}
if(current.right != null){
list.add(current.right);
}
index ++;
if(index == list.size()){
break;
}
current = list.get(index);
}
int[] ans = new int[index];
for(int i = 0; i < index; i ++){
ans[i] = list.get(i).val;
}
return ans;
}
}
shuaidi
共以下 24 个回答
层序打印，用deque
LCR 149. 彩灯装饰记录 I
时间O(N)，空间O(N)
中文 decorateRecord(TreeNode* root) { result; cur=node.front();
class Solution {
public:
vector
queue<TreeNode> node;
vector
if(root!=nullptr){
node.push(root);
}
while(!node.empty()){
TreeNode
node.pop();
result.push_back(cur->val);
};
题解
使用队列先进先出的性质，先遍历到的会被记录下来，再复杂操作中可以把数据放到队列里面暂存
方法：BFS 将每个字结构的根节点放入queue中，然后根据queue FIFO的原理来将左边的值先塞入结果的stack中。
time O(n) space O(n)
层序遍历基础
用队列记录每一层的节点，从左到右，实现一个个输出
on on
思路：层序遍历，队列存每一层的节点，记录节点数，循环完当前层之后进入下一层
时间复杂度O(N),空间复杂度O(N)
时间o(n)
空间o(n)
通过队列实现非递归遍历
时间复杂度O(N)，空间复杂度O(N)。
时间复杂度O(n), 空间复杂度O(n)
打卡
//需要一个辅助队列，每次弹出一个节点，输出他的值，并把他的左右孩子压入队列，直到队列为空 queue = new LinkedList<>(); arr = new ArrayList ();
class Solution {
public int[] decorateRecord(TreeNode root) {
Queue
List
// int[] result = arr.stream().mapToInt(Integer::intValue).toArray();
int [] result = new int [n];
int i = 0;
for (int j : arr) {
result[i] = j;
i++;
}
}
class Solution { deque = new ArrayDeque(); list = new ArrayList();
public int[] decorateRecord(TreeNode root) {
if(root null) return new int[]{};
Deque
deque.offer(root);
List
while(!deque.isEmpty()){
int size = deque.size();
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);
}
}
}
int[] res = new int[list.size()];
for(int i = 0; i < res.length; i++){
res[i] = list.get(i);
}
return res;
}
}
层次遍历
时间：O（n）
空间：O（n）
简单的队列层序遍历
时间复杂度O(n)
空间复杂度O(n)
思路： 使用 队列操作
思路：使用队列辅助存储二叉树节点，层序遍历逐层处理节点，并将节点值存储在集合中，最后转换为数组即可。
时间复杂度：O(n)，每个节点都需要遍历一次。
空间复杂度：O(n)，
list会存储所有的节点值。