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

YOLO 普通 2024年3月28日下午12:40

 /*从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。 */
class Solution {
    public int[] decorateRecord(TreeNode root) {
        if(root == null)
            return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();  //定义一个队列(先进先出)，存储查找的节点过程
        List<Integer> res = new ArrayList<>();  //定义一个数组，存储查找完的节点

        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            res.add(t.val);
            if(t.left != null){
                queue.add(t.left);
            }
            if(t.right != null){
                queue.add(t.right);
            }
        }
        int[] arr = new int[res.size()];  //定义一个数组打印，长度为之前的数组长度
        for(int i = 0;i < res.size();i++){
        arr[i] = res.get(i);  //get得到数据
        }
        return arr;
    }
}

0 赞同 0 条回复

kfaebot 普通 2024年3月14日下午5:30

/**
 * 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<int> decorateRecord(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;

        if(root!=nullptr){
            que.push(root);
        }
        while(!que.empty()){
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode* tmp=que.front();
                que.pop();
                result.push_back(tmp->val);
                if(tmp->left!=nullptr){
                    que.push(tmp->left);
                }
                if(tmp->right!=nullptr){
                    que.push(tmp->right);
                }
            }
        }
        return result;
    }
};
//时间复杂度O(N)
//空间复杂度O(N)

0 赞同 0 条回复

东普通 2024年3月12日下午8:27

~~~java
//就是使用层序遍历，BFS使用队列作为辅助
//int[]是没有函数直接添加元素的，所以要用ArrayList过渡一下
class Solution {
public int[] decorateRecord(TreeNode root) {
if(root null) return new int[0];
Queue queue = new LinkedList<>();
ArrayList ans = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
ans.add(node.val);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
int[] res = new int[ans.size()];
for(int i = 0; i < ans.size(); i++)
res[i] = ans.get(i);
return res;
}
}
java

0 赞同 0 条回复

　南木普通 2024年3月12日下午7:06

层序遍历,需要一个辅助队列

/**
 * 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 int[] decorateRecord(TreeNode root) {
        int[] arr = {};
        if(root == null)
            return arr;
        Queue<TreeNode> q = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode temp = q.peek();
            if(temp.left != null){
                q.add(temp.left);
            }
            if(temp.right != null){
                q.add(temp.right);
            }
            list.add(q.poll().val);
        }
        arr = list.stream().mapToInt(Integer::intValue).toArray();

        return arr;
    }
}

0 赞同 0 条回复

一个达不刘普通 2024年3月12日下午3:09

class Solution {
public:
//层序遍历，辅助队列
vector arr ;
vector decorateRecord(TreeNode* root) {
if(root nullptr) return {};
queue que;
que.push(root);//根结点入队
while(!que.empty()){//队列非空
TreeNode *node = que.front();//队头结点出队
que.pop();
arr.push_back(node->val);//存到数组
if(node->left) que.push(node->left);//左孩子入队
if(node->right) que.push(node->right);//右孩子入队
}
return arr;
}
};

0 赞同 0 条回复

RunAsOne 普通 2024年3月12日下午3:02

第n次打卡

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):

    def decorateRecord(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        queue = collections.deque()
        queue.append(root)
        while queue:
            tmp = queue.popleft()
            res.append(tmp.val)
            if tmp.left:
                queue.append(tmp.left)
            if tmp.right:
                queue.append(tmp.right)

        return res

0 赞同 0 条回复

MARS 普通 2024年3月11日下午9:59

day8第一题

function decorateRecord(root: TreeNode | null): number[] {
    if(root == null) return []    
    let queue = [root],num=1  //用队列，num计算现在一层多少个节点
    let res = []
    while(queue.length>0){
        let count=0
        while(num !=0){  //将该层全部元素全部拿出
            let node = queue.shift()
            res.push(node.val)
            if(node.left){
                queue.push(node.left)
                count++
            }
             if(node.right){
                queue.push(node?.right)
                count++
            }
            num--
        }
        num = count  //将下一层数目给到num
    }
    return res
};

0 赞同 0 条回复

言之命至普通 2024年3月11日下午9:07

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null){
            return new int[0];
        }

        Queue<TreeNode> queue = new LinkedList<>(); //定义一个队列
        List<Integer> res = new ArrayList<>();

        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            res.add(t.val);
            if(t.left != null) queue.add(t.left);
            if(t.right != null) queue.add(t.right);
        }

        int[] arr = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            arr[i] = res.get(i);
        }

        return arr;

    }
}

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月11日下午8:32

class Solution {
    // 利用队列先进先出的特性
    // 用循环对二叉树进行层序遍历
    // 将每一层的节点放入队列中，将上层节点放入列表中
    public int[] decorateRecord(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<Integer> ans = new ArrayList<>(1000);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }
    // 时间复杂度为 O(n)
    // 每一个节点都要进入队列
    // 空间复杂度为 O(n)
}

0 赞同 0 条回复

Free 普通 2024年3月11日下午8:05

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

时空复杂度O(n)

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月11日下午7:44

这题思路不难，就是很多琐碎的东西。其实这题可以分为4个大板块：判断特殊情况，初始化队列和列表，核心代码，返回结果
class Solution {
public int[] levelOrder(TreeNode root) {
if(root null){
return new int[0];
}

    Queue<TreeNode> queue = new LinkedList<>();
    List<Integer> res = new ArrayList<>();

    queue.add(root);
    while(!queue.isEmpty()){
        TreeNode t = queue.poll();
        res.add(t.val);
        if(t.left != null) queue.add(t.left);
        if(t.right != null) queue.add(t.right);
    }

    int[] arr = new int[res.size()];
    for(int i = 0; i < res.size(); i++){
        arr[i] = res.get(i);
    }

    return arr;

}

}

0 赞同 0 条回复

mpweixin用户普通 2024年3月11日下午2:17

public int[] decorateRecord(TreeNode root) {
if(root null) return new int[0];
Queue q = new LinkedList<>(){{ add(root); }};
ArrayList ans =new ArrayList<>();
while(!q.isEmpty()){
TreeNode node =q.poll();
ans.add(node.val);
if(node.left!=null) q.add(node.left);
if(node.right!=null) q.add(node.right);
}
int[] res=new int[ans.size()];
for(int i=0;i<ans.size();i++){
res[i]=ans.get(i);
}
return res;

思路：利用队列实现广度优先遍历

0 赞同 0 条回复

南梁陈庆之普通 2024年3月11日上午11:23

广度优先算法，层序遍历

/**
 * 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 int[] decorateRecord(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
}

0 赞同 0 条回复

神经蛙普通 2024年3月10日下午11:50

class Solution {
public:
vector decorateRecord(TreeNode* root) {
vector res;
if(!root) return res;
queue que;
que.push(root);
while(!que.empty()){
TreeNode* node = que.front();
que.pop();
res.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
return res;
}
};
打卡

0 赞同 0 条回复

helloMoon 普通 2024年3月10日下午11:15

从上到下打印二叉树java

/**
 * 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 int[] decorateRecord(TreeNode root) {
        if(root == null){
            return new int[0];
        }

        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();

        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            res.add(t.val);
            if(t.left != null) queue.add(t.left);
            if(t.right != null) queue.add(t.right);
        }

        int[] arr = new int[res.size()];
        for(int i = 0; i < res.size(); i ++ ){
            arr[i] = res.get(i);
        }

        return arr;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月10日下午9:34

java
class Solution{
public int[] decorateRecord(TreeNode root){
if(root null) return new int[0];
Queue queue = new LinkedList<>(){{add(root);}};
ArrayList ans = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode node = queue.poll();
ans.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
int[] res = new int[ans.size()];
for(int i = 0; i < ans.size(); i++){
res[i] = ans.get(i);
}
return res;
}
}
时间复杂度 O(N)
空间复杂度 O(N)

0 赞同 0 条回复

方铎码农普通 2024年3月10日下午5:23

class Solution {
    public int[] decorateRecord(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            res.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }

        int[] ans = new int[res.size()];
        for(int i = 0; i < res.size(); i++)
            ans[i] = res.get(i);

        return ans;
    }
}

时间复杂度$O(n)$，额外空间复杂度： $O(n)$

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月10日下午3:48

class Solution {
    public int[] decorateRecord(TreeNode root) {
        if(root == null){
            return new int[0];
        }
        Queue<TreeNode> q = new LinkedList<>();
        List<Integer> res=new ArrayList<>();

        q.add(root);
        while(!q.isEmpty()){
            TreeNode temp=q.poll();
            res.add(temp.val);
            if(temp.left!=null){
                q.add(temp.left);
            }
            if(temp.right!=null){
                q.add(temp.right);
            }
        }

        int[] arr = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            arr[i] = res.get(i);
        }

        return arr;

    }
}

时间复杂度：O(n)
额外空间复杂度： O(n)

0 赞同 0 条回复

Jimmy 普通 2024年3月10日下午3:32

层序遍历，时间复杂度和空间复杂度为O(n)

/**
 * 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<int> decorateRecord(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> que;
        if(root){
            que.push(root);
        }

        while(!que.empty()){

            for(int i=0;i<que.size();i++){
                TreeNode *cur = que.front();
                ans.push_back(cur->val);
                que.pop();
                if(cur->left)que.push(cur->left);
                if(cur->right)que.push(cur->right);
            }
        }
        return ans;
    }
};

0 赞同 0 条回复

Yuki 永久会员 2024年3月10日上午10:41

纯纯层序遍历

class Solution {
public:
vector decorateRecord(TreeNode* root) {
vectorres;
queue<TreeNode*>que;

    if(root==nullptr)return res;
    que.push(root);

    while(!que.empty()){
        int size=que.size();

        for(int i=0;i<size;i++){
            TreeNode*node=que.front();
            res.push_back(node->val);
            que.pop();

            if(node->left)que.push(node->left);
            if(node->right)que.push(node->right);
        }
    }
    return res;
}

};

时间复杂度：O（N）
空间复杂度：O（N）

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月10日上午9:31

打卡

class Solution {
public:
    vector<int> decorateRecord(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> que;
        vector<int> res;
        que.push(root);

        while(!que.empty()) {
            TreeNode* cur = que.front(); que.pop();
            res.emplace_back(cur->val);
            if(cur->left) que.push(cur->left);
            if(cur->right) que.push(cur->right);
        }
        return res; 
    }
};

0 赞同 0 条回复

进取普通 2024年3月9日下午11:55

class Solution {
public:
vector decorateRecord(TreeNode* root) {
if (root nullptr) return {};
vector ret;
queue<TreeNode> q;
q.push(root);
while (!q.empty()){
TreeNode tmp = q.front();
ret.push_back(tmp->val);
q.pop();
if (tmp->left) q.push(tmp->left);
if (tmp->right) q.push(tmp->right);
}
return ret;
}
};时空复杂度O(N)

0 赞同 0 条回复

=.= 普通 2024年3月9日下午11:46

/**
* 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 int[] decorateRecord(TreeNode root) {
if(root null) return new int[0];
List res = new ArrayList<>();

    Deque<TreeNode> queue = new ArrayDeque<>();

    queue.addLast(root);
    while(!queue.isEmpty()){
        TreeNode node = queue.removeFirst();
        res.add(node.val);
        if(node.left != null) queue.addLast(node.left);
        if(node.right != null) queue.addLast(node.right);
    }
    int[] ans = new int[res.size()];
    for(int i=0; i<res.size(); i++){
        ans[i] = res.get(i);
    }
    return ans;
}

}

时空复杂度O(n)

0 赞同 0 条回复

heathhou 普通 2024年3月9日下午10:06

class Solution {
public:
    vector<int> decorateRecord(TreeNode* root) {
        vector<int> result;
        // 判断root是否为空
        if(!root)
            return result;

        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* p = q.front();
            q.pop();
            if(p != nullptr)    
                result.push_back(p->val);
            if(p->left != nullptr)  
                q.push(p->left);
            if(p->right != nullptr) 
                q.push(p->right);
        }

        return result;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年3月9日下午10:02

class Solution {
public int[] decorateRecord(TreeNode root) {
if(root null)
return new int[0];
List ans = new ArrayList<>();
Queue list = new LinkedList<>();
list.add(root);
while(!list.isEmpty()){
TreeNode temp = list.remove();
ans.add(temp.val);
if(temp.left!=null)
list.add(temp.left);
if(temp.right!=null)
list.add(temp.right);
}
int[] ansI = new int[ans.size()];
for(int i = 0; i < ans.size(); i++){
ansI[i] = ans.get(i);
}
return ansI;

}
时空复杂度均为On

0 赞同 0 条回复

机电皮怪永久会员 2024年3月9日下午9:41

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

“`C++
class Solution {
public:
vector decorateRecord(TreeNode* root)
{
vector result;
if(root == nullptr)
{
return {};
}
queue tmp;
tmp.push(root);
while(tmp.empty() != true)
{
TreeNode* temp = tmp.front();
tmp.pop();
result.push_back(temp->val);
if(temp->left != nullptr)
{
tmp.push(temp->left);
}
if(temp->right != nullptr)
{
tmp.push(temp->right);
}
}
return result;
}
};
“`

0 赞同 0 条回复

Raphtalia. 普通 2024年3月9日下午7:30

/**
* 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 decorateRecord(TreeNode root) {
queue<TreeNode> q;
vector ans;
if(!root) return ans;
q.push(root);
while(!q.empty()){
TreeNode cur = q.front();
q.pop();
ans.push_back(cur->val);
if(cur->left != nullptr) q.push(cur->left);
if(cur->right != nullptr) q.push(cur->right);
}

    return ans;
}

};//时间复杂度O（n）空间复杂度O(n）

0 赞同 0 条回复

莫～慢～待普通 2024年3月9日下午7:06

class Solution {
public int[] decorateRecord(TreeNode root) {
int[] res;
if(rootnull)
{
res=new int[0];
return res;
}
Queue queue=new LinkedList<>();
List list_res=new ArrayList<>();
queue.offer(root);
while(!queue.isEmpty())
{
TreeNode node=queue.poll();
list_res.add(node.val);
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
res=new int[list_res.size()];
for(int i=0;i<list_res.size();i++)
{
res[i]=list_res.get(i);
}
return res;
}
}
层次遍历

0 赞同 0 条回复

王位詮釋普通 2024年3月9日下午6:23

class Solution {
    public int[] decorateRecord(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while(!deque.isEmpty()){
            TreeNode temp = deque.poll();
            if(temp==null){
                continue;
            }
            result.add(temp.val);
            deque.offer(temp.left);
            deque.offer(temp.right);
        }
        int[] ret = new int[result.size()];
        for(int i=0;i<result.size();i++){
            ret[i] = result.get(i);
        }
        return ret;
    }
}
思路：使用队列，如果队列不为空就执行循环体：
将队列头元素出队，如果这个元素不为空的话，将其val加入结果，同时将其left和right入队直到遍历完所有层。
时间复杂度：遍历了树的所有节点，所以是O(n)
空间复杂度：返回值不算空间复杂度的话，因为使用了额外的队列以及动态数组这些数据结构，且动态数组最长为树长，O(n)

0 赞同 0 条回复

紫芝普通 2024年3月9日下午5:32

思路：层序遍历

func decorateRecord(root *TreeNode) []int {
    var res []int
    if root == nil { return res }
    var que []*TreeNode
    que = append(que, root)
    for len(que) > 0 {
        n := len(que)
        for i := 0; i<n; i++ {
            cur := que[i]
            res = append(res, cur.Val)
            if cur.Left != nil { que = append(que, cur.Left) }
            if cur.Right != nil { que = append(que, cur.Right) }
        }
        que = que[n:]
    }
    return res
}

0 赞同 0 条回复

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

共以下 30 个回答

# 回答此问题取消回复

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

共以下 30 个回答

# 回答此问题 取消回复

# 回答此问题取消回复