【二叉树专题】剑指 Offer 32 – II. 从上到下打印二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

岱永久会员 2024年12月18日下午10:48

LCR 150. 彩灯装饰记录 II

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        if(root != null ) queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size() ;i>0;i--){  //易错。for循环从高到底，避免size改变
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);

            }
            ans.add(tmp);
        }
        return ans;
    } 
}

0 赞同 0 条回复

mpweixin用户普通 2024年12月16日下午11:49

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> result;
        if(root == NULL) return result;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int num = q.size();
            vector<int> t_result;
            while(num != 0){
                TreeNode* temp = q.front();
                q.pop();
                num--;
                t_result.push_back(temp->val);
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            }
            result.push_back(t_result);
        }
        return result;
    }
};

时间O(N), 空间O(N)

0 赞同 0 条回复

晓宇普通 2024年12月16日上午11:13

class Solution {
public:
    // 层序遍历 每层需要标记
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root)  return ans;

        queue<TreeNode*> q{{root}}; // 层序遍历队列
        while (!q.empty()) {
            int n = q.size();
            vector<int> level;
            for (int i = 0; i < n; ++i) {
                TreeNode* tmp = q.front();
                q.pop();
                level.push_back(tmp->val);
                if (tmp->left) q.push(tmp->left);

                if (tmp->right) q.push(tmp->right);

            }
            ans.push_back(level);
        }
        return ans;
    }
        // o(n) o(w)
};

0 赞同 0 条回复

🌟 普通 2024年12月14日下午6:03

class Solution {
public:
vector<vector> decorateRecord(TreeNode* root) {
queue<TreeNode> node;
vector<vector> result;
if(root!=nullptr){
node.push(root);
}
while(!node.empty()){
vector temp;
int size=node.size();
for(int i=0;i<size;++i)
{
TreeNode cur=node.front();
node.pop();
temp.push_back(cur->val);

            if(cur->left) node.push(cur->left);
            if(cur->right) node.push(cur->right);
        }
        result.push_back(temp);
    }
    return result;
}

};
中文

0 赞同 0 条回复

陆狗陆狗普通 2024年12月4日下午10:08

题解
跟上面那一题的思路是相同的，只是需要知道每一层有多少个，可以通过队列api，.size()去获取

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        if(root==null){
            // 错误点：int[]的new的方式
            return new ArrayList(0);
        }
        // 定义队列去按照访问顺序放入元素
        // 错误点:泛型元素的声明
        Queue<TreeNode> q= new LinkedList();
        // 定义链表存放值（因为个数不确定，不能建立数组了）
        List<List<Integer>> resultList=new ArrayList();
        q.offer(root);
        while(!q.isEmpty()){
            // 每一行的长度
            int rowSize=q.size();
            // 存放一行节点的数据
            List<Integer> innerReslut=new ArrayList(rowSize);
            for(int i=0;i<rowSize;i++){
                TreeNode tmpt= q.poll();
                innerReslut.add(tmpt.val);
                // 左右节点放入队列中
                if(tmpt.left!=null){
                    q.offer(tmpt.left);
                }
                if(tmpt.right!=null){
                    q.offer(tmpt.right);
                }
            }
            // 值放入list中
            resultList.add(innerReslut);
        }
        return resultList;
    }
}

0 赞同 0 条回复

Tom Yuan 普通 2024年12月4日上午8:11

方法：用队列，但是缓存当前层级的长度，以此来确定哪些值是在同一层的。
用两个while loop 大的while用来走完整个树小的用来走完整个层级并把同一个层级的值放在同一个数组中。

# 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
class Solution:
    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue: deque[TreeNode] = deque()
        queue.append(root)
        stack = []
        while queue:
            size_row = len(queue) # 当一个层级走完时，重新更新queue中的长度
            row = []
            while size_row: # 用缓存的层级长度来进行pop和找左右节点操作
                node = queue.popleft()
                row.append(node.val)
                size_row -= 1
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            stack.append(row)
        return stack

time O(n) space O(n)

0 赞同 0 条回复

无言永久会员 2024年12月3日下午5:29

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty()) {
            int len = que.size();
            vector<int> temp;
            while(len--) {
                TreeNode* node = que.front();
                temp.push_back(node->val);
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            ans.push_back(temp);
        }
        return ans;
    }
};
时间复杂度：O(n) 
空间复杂度：O(n)

0 赞同 0 条回复

休一普通 2024年12月2日下午10:50

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
         vector<vector<int>> result;
         queue<TreeNode*> qu;
         //size用于记录每一层的节点数量
         int size = 0;
         if(!root) return result;
         qu.push(root);
         while(!qu.empty())
         {
            vector<int> value;
            size = qu.size();
            while(size--)
            {
                TreeNode* temp = qu.front();
                qu.pop();
                value.push_back(temp->val);
                if(temp->left) qu.push(temp->left);
                if(temp->right) qu.push(temp->right);
            }
            result.push_back(value);         
         }
         return result;
    }
};

使用size来标记每一层的节点数目
时间和空间复杂度均为o(n)

0 赞同 0 条回复

Pendulumpal 普通 2024年12月2日下午9:26

模板题

    public List<List<Integer>> decorateRecord(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null)return res;
        Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};
        while(!queue.isEmpty()) {
            List<Integer>tmp=new ArrayList<>();
            for(int i=queue.size();i>0;i--){
                TreeNode node=queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午6:09

/**
方法一：层次遍历模版，时间复杂度O(N), 空间复杂度O(N)
 */
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);

        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);
                }
            }

            res.add(oneRes);

        }

        return res;

    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年11月30日下午3:10

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null)
            return res;
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> resList=new ArrayList();
            for(int i = queue.size(); i > 0; i--){   //q.size()会随每一次q.poll()而减少,所以必须从高到低定义循环
                TreeNode tmp=queue.poll();
                resList.add(tmp.val);
                if(tmp.left!=null) queue.offer(tmp.left);
                if(tmp.right!=null) queue.offer(tmp.right);
            }
            res.add(resList);
        }
        return res;
    }
}
时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

Renasc 普通 2024年11月29日下午9:50

时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        // 如果root为空，返回一个空List
        if (root == null) return new ArrayList<>();

        // 创建队列和结果集合
        Queue<TreeNode> queue = new LinkedList<>(){{offer(root);}};  // 加入根节点
        List<List<Integer>> res = new ArrayList<>();

        // 开始遍历队列
        while (!queue.isEmpty()) {
            // 创建每一层的临时集合
            List<Integer> temp = new ArrayList<>();

            for (int i=queue.size(); i>0; i--) {
                // 队列出队
                TreeNode node = queue.poll();
                // 把队列加入temp
                temp.add(node.val);
                // 遍历左右子树
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            // 把每一层加到总结果集合中
            res.add(temp);
        }
        // 返回结果集合
        return res;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年11月29日下午9:22

在上面一题的基础上每一层输出在一起，就只用再来一个for循环，最大次数是队列长度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        List<List<Integer>> res =new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null)queue.add(root);


<pre><code>    while(!queue.isEmpty()){
        List<Integer> list=new ArrayList<>();
        for(int i=queue.size();i>0;i--){
            TreeNode node=queue.poll();
            list.add(node.val);
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
        }

        res.add(list);
    }

    return res;
}
</code></pre>

}

on on

0 赞同 0 条回复

黑键〰普通 2024年11月29日下午7:17

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var decorateRecord = function(root) {
    if(!root) return []
    let q = [root]
    let res = []
    while(q.length > 0) {
        let len = q.length
        let level = []
        while(len) {
            let cur = q.shift()
            if(cur.left) q.push(cur.left)
            if(cur.right) q.push(cur.right)
            level.push(cur.val)
            len--
        }
        res.push(level)
    }
    return res
};

思路：在上一题的基础上加上对每一层存入队列即可
时间复杂度和空间复杂度都是O(N)

0 赞同 0 条回复

Jerry 普通 2024年11月29日下午3:38

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int sz = q.size();
            vector<int> res;
            for(int i = 0; i < sz; i++){
                TreeNode* tmp = q.front();
                res.push_back(tmp->val);
                q.pop();
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            ans.push_back(res);
        }
        return ans;
    }
};

时间o(n)
空间o(n)
跟上一题没啥区别

0 赞同 0 条回复

Aatorx 永久会员 2024年11月29日下午3:19

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr){
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            vector<int> v;
            int n = q.size();
            for(int i = 0; i<n; i++){
                TreeNode* temp = q.front();
                q.pop();
                v.push_back(temp->val);
                if(temp->left != nullptr){
                    q.push(temp->left);
                }
                if(temp->right != nullptr){
                    q.push(temp->right);
                }
            }
            res.push_back(v);
        }
        return res;
    }
};

时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

月下足迹普通 2024年11月29日上午11:11

//双重循环，内循环遍历每一层的节点
public List<List> decorateRecord1(TreeNode root) {
Queue queue = new LinkedList<>();
List<List> result = new ArrayList<>();
if (root != null) queue.add(root);

    while(!queue.isEmpty()) {
        List<Integer> tmp = new ArrayList<>();
        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);
        }
        result.add(tmp);
    }
    return result;
}

0 赞同 0 条回复

youngsir 普通 2024年11月29日上午10:55

打卡

/**
 * 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>> res;
        if(root == nullptr){
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int n =q.size();
            vector<int> ans;
            for(int i = 0 ; i < n; i++){
                TreeNode* temp = q.front();
                q.pop();
                ans.push_back(temp->val);
                if(temp->left){
                    q.push(temp->left);
                }
                if(temp->right){
                    q.push(temp->right);
                }


            }
            res.push_back(ans);
        }
        return res;

    }
};

0 赞同 0 条回复

苯庸普通 2024年11月29日上午9:45

class Solution {
public List<List> decorateRecord(TreeNode root) {
List<List> res = new ArrayList();
if(root null) return res;
Deque deque = new ArrayDeque();
deque.offer(root);
while(!deque.isEmpty()){
int size = deque.size();
List list = new ArrayList();
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);
}
}
res.add(list);
}
return res;
}
}
层次遍历
时间：O（n）
空间：O（n）

0 赞同 0 条回复

jaron 普通 2024年11月29日上午9:44

要区分每一层，每次遍历之前记录队列的大小

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<>();
        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);
            }
            res.add(sub);
        }
        return res;
    }
}

0 赞同 0 条回复

lQl 永久会员 2024年11月28日下午10:34

队列+小循环

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);
        while (!tree.isEmpty()) {
            int num = tree.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < num; i++) {
                if (tree.peek().left != null)
                    tree.offer(tree.peek().left);
                if(tree.peek().right!=null)
                    tree.offer(tree.peek().right);
                tmp.add(tree.poll().val);
            }
            ans.add(tmp);
        }
        return ans;
    }
}

时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

秋山丽奈普通 2024年11月28日下午8:21

思路：使用队列实现

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {

        if(root == null){
            return new ArrayList<List<Integer>>(){}; 
        }

        List<TreeNode> list = new ArrayList<>();
        List<Integer> listVal = new ArrayList<>();
        List<List<TreeNode>> ans = new ArrayList<List<TreeNode>>();
        List<List<Integer>> ansVal = new ArrayList<List<Integer>>();

        list.add(root);
        listVal.add(root.val);
        ans.add(list);
        ansVal.add(listVal);

        int index = 0;
        while(true){
            List<TreeNode> current = ans.get(index);

            List<TreeNode> temp = new ArrayList<TreeNode>();
            List<Integer> tempVal = new ArrayList<>();
            for(int i = 0; i < current.size(); i ++){
                TreeNode currentNode = current.get(i);

                if(currentNode.left != null){
                    temp.add(currentNode.left);
                    tempVal.add(currentNode.left.val);
                }
                if(currentNode.right != null){
                    temp.add(currentNode.right);
                    tempVal.add(currentNode.right.val);
                }

            }

            if(temp.size() == 0){
                break;
            }
            index ++;
            ans.add(temp);
            ansVal.add(tempVal);
        }

        return ansVal;
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年11月28日下午8:03

class Solution {
    /**
     * 对二叉树进行层序遍历，返回每一层的节点值列表
     * 层序遍历是一种从上到下，从左到右逐层访问树节点的遍历方式
     * 
     * @param root 二叉树的根节点
     * @return 返回一个列表，其中每个元素代表树的一层节点值
     */
    public List<List<Integer>> decorateRecord(TreeNode root) {
        // 初始化结果列表
        List<List<Integer>> res = new ArrayList<>();
        // 如果根节点为空，直接返回空的结果列表
        if (root == null) {
            return res;
        }

        // 使用队列辅助进行层序遍历
        Queue<TreeNode> que = new LinkedList<>();
        // 将根节点加入队列开始遍历
        que.offer(root);

        // 当队列不为空时，继续遍历
        while (!que.isEmpty()) {
            // 获取当前层的节点数量
            int size = que.size();
            // 初始化当前层的节点值列表
            List<Integer> level = new ArrayList<>();
            // 此时的 for 循环，遍历的就是同一层的节点
            for (int i = 0; i < size; i++) {
                // 出队当前层的节点
                TreeNode node = que.poll();
                // 将节点值加入当前层的列表中
                level.add(node.val);
                // 如果当前节点有左子节点，加入队列以供下一层遍历
                if (node.left != null) {
                    que.offer(node.left);
                }
                // 如果当前节点有右子节点，加入队列以供下一层遍历
                if (node.right != null) {
                    que.offer(node.right);
                }
            }
            // 将当前层的节点值列表加入结果列表中
            res.add(level);
        }
        // 返回结果列表
        return res;
    }
}

思路：使用队列实现层序遍历，对每一层的节点存储在集合中，每一层遍历完后存储到 res 中。
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

【二叉树专题】剑指 Offer 32 – II. 从上到下打印二叉树

共以下 23 个回答

LCR 150. 彩灯装饰记录 II

# 回答此问题取消回复

【二叉树专题】剑指 Offer 32 – II. 从上到下打印二叉树

共以下 23 个回答

LCR 150. 彩灯装饰记录 II

# 回答此问题 取消回复

# 回答此问题取消回复