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

九号球普通 2023年11月15日下午10:50

“`java
一个字，层序遍历
class Solution {
public int[] decorateRecord(TreeNode root) {
List list = new ArrayList<>();
if (root == null) {
return new int[0];
}
Queue q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()) {
TreeNode node = q.poll();
list.add(node.val);
if (node.left != null) {
q.add(node.left);
}
if (node.right != null) {
q.add(node.right);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; } }

0 赞同 0 条回复

大大普通 2023年11月15日下午9:05

c++
 //层序遍历
class Solution {
public:
    vector<int> decorateRecord(TreeNode* root) {
     vector<int> ans;
     if(root==NULL)return ans;
     queue<TreeNode*>q;
     q.push(root);
     while(!q.empty()){
      TreeNode* h=q.front();
      q.pop();
      ans.push_back(h->val);
      if(h->left)q.push(h->left);
      if(h->right)q.push(h->right);
     }
         return ans;

    }
};

0 赞同 0 条回复

招舟子普通 2023年8月25日下午7:47

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {

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

}
1111采用队列

0 赞同 0 条回复

jhfuture 普通 2023年8月11日下午10:05

“`java
public int[] levelOrder(TreeNode root) {
if (root==null) {
return new int[0];
}
// 使用队列
Queue queue= new LinkedList();
List result=new ArrayList();

        queue.add(root);
        while(!queue.isEmpty()){
          TreeNode  t= queue.poll();
            result.add(t.val);
            if(t.left!=null) queue.add(t.left);
            if(t.right!=null) queue.add(t.right);
        }
        int[] re=new int[result.size()];
        for(int i=0;i<result.size();i++){
            re[i]=(result.get(i)).intValue();
        }
        return re;

}

0 赞同 0 条回复

淡色花樱普通 2023年7月20日下午11:32

“`java
class Solution{
public int[] levelOrder(TreeNode root){
if(root == null){
return new int[0];
}
Queue queue = new LinkList<>();
List 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

0 赞同 0 条回复

cute. 普通 2023年7月18日下午6:01

思路：递归

var levelOrder = function(root) {
    if(root === null) return [];
    let queue = [];
    let res = [];
    queue.push(root);
    while(queue.length > 0) {
        let t = queue.shift();
        res.push(t.val);
        if(t.left !== null) queue.push(t.left);
        if(t.right !== null) queue.push(t.right);
    }
    return res;
};

0 赞同 0 条回复

断舍离永久会员 2023年7月10日下午4:01

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        //根节点为null特殊情况
        if(root == null){
            return new int[0];
        }
        //非递归队列
        LinkedList<TreeNode> queue = new LinkedList();
        //按层序从左到右加入集合
        ArrayList<Integer> list = new ArrayList<>();
        queue.add(root);
        //若队列不为空，说明二叉树未遍历完
        while (!queue.isEmpty()){
            TreeNode node = queue.remove();
            if(node != null){
                list.add(node.val);
                queue.add(node.left);
                queue.add(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 条回复

mpweixin用户普通 2023年7月8日下午4:36

C++实现

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> q;
        if(!root) return result;


        q.push(root);
        while(!q.empty()){

            result.push_back(q.front() -> val);
            TreeNode* temp = q.front();
            q.pop();
            if(temp -> left != nullptr){
                q.push(temp -> left);
            }
            if(temp -> right != nullptr){
                q.push(temp -> right);
            }
        }
        return result;


    }
};

0 赞同 0 条回复

CV大神普通 2023年7月7日下午9:42

 public int[] levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> values = new ArrayList<>();
        if (root != null) {
            queue.addLast(root);
        }
        //画个图更好理解
        while (!queue.isEmpty()) {
            TreeNode node = queue.pollFirst();
            values.add(node.val);
            if (node.left != null) {
                queue.addLast(node.left);
            }
            if (node.right != null) {
                queue.addLast(node.right);
            }
        }
        //转成数组
        int[] array = new int[values.size()];
        for (int i = 0; i < values.size(); i++) {
            array[i] = values.get(i);
        }
        return array;
    }

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

0 赞同 0 条回复

憨憨永久会员 2023年7月7日下午5:43

通过队列完成层序遍历，然后将每层的数据储存

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null)return new int[0];
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        ArrayList<Integer> list=new ArrayList<>();
        while(!queue.isEmpty()){
            int a=queue.size();
            TreeNode temp=null;
            for(int i=0;i<a;i++){
                temp=queue.poll();
                list.add(temp.val);
                if(temp.left!=null){
                    queue.offer(temp.left);
                }
                if(temp.right!=null){
                    queue.offer(temp.right);
                }
            }
        }
        int[] ans=new int[list.size()];
        for(int i=0;i<ans.length;i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}

0 赞同 0 条回复

BOZ 普通 2023年7月7日下午12:45

【思路】用C++ STL queue库的接口完成遍历
【复杂度】时间O(n)，空间O(n)

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        std::queue<TreeNode*> q;
        std::vector<int> result;
        q.push(root);
        while(!q.empty()) {
            auto node = q.front();
            q.pop();
            if (node == NULL) continue;
            result.push_back(node->val);
            q.push(node->left);
            q.push(node->right);
        }
        return result;
    }
};

0 赞同 0 条回复

Sexypig. 普通 2023年7月6日下午12:13

思路：

首先创建一个空的队列和一个空的结果数组。
将根节点入队。
进入循环，直到队列为空。
在每次循环中，取出队首元素，将其值存入结果数组。
如果当前节点有左子节点，则将左子节点入队。
如果当前节点有右子节点，则将右子节点入队。
循环结束后，返回结果数组。
这段代码实现了对二叉树进行层次遍历，即从上到下逐层遍历二叉树的节点，并将节点的值按顺序存储在结果数组中。
通过使用队列来辅助实现层次遍历，可以保证先遍历父节点，再遍历子节点，从而保证了层次遍历的顺序性。

#include<iostream>
#include<vector>
#include<queue>


using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans; // 用于存储结果的数组
        queue<TreeNode*> q; // 用于进行层次遍历的队列
        q.push(root); // 将根节点入队
        TreeNode* cur = nullptr; // 用于存储当前节点的指针

        while (!q.empty()) { // 队列不为空时执行循环
            cur = q.front(); // 获取队首元素
            q.pop(); // 弹出队首元素

            ans.push_back(cur->val); // 将当前节点的值存入结果数组

            if (cur->left) // 如果当前节点有左子节点，则将其入队
                q.push(cur->left);
            if (cur->right) // 如果当前节点有右子节点，则将其入队
                q.push(cur->right);
        }

        return ans; // 返回结果数组
    }
};

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午2:16

队列

class Solution {
    public int[] levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        if(root==null)
            return new int[0];
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;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[] p = new int[list.size()];
        int index=0;
        for(Integer i:list)
            p[index++]=i;
        return p;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月4日上午9:51

java
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) {
            return new int[0];
        }
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode tmp = root;
        q.add(root);
        while(q.size() != 0) {
            tmp = q.poll();
            res.add(tmp.val);
            if(tmp.left != null) {
                q.add(tmp.left);
            }
            if(tmp.right != null) {
                q.add(tmp.right);
            }
        }
        int[] arr = new int[res.size()];
        for(int i = 0; i < res.size(); i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }
}

遍历了每个节点时间复杂度O(N), 使用队列和ArrayList空间复杂度O(N)

0 赞同 0 条回复

局外人普通 2023年7月3日下午9:31

思路：层序遍历，使用队列作为辅助数据结构
时间复杂度O(n) 空间复杂度O(n)

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null)  return new int[0];
        Queue<TreeNode> q = new LinkedList<>();
        ArrayList<Integer> a = new ArrayList<>();
        q.offer(root);

        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            a.add(cur.val);

            if(cur.left!=null)    q.offer(cur.left);
            if(cur.right!=null)   q.offer(cur.right);

        }

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月2日上午12:06

int* levelOrder(struct TreeNode* root, int* returnSize){
    * returnSize = 0;
    if(!root){
        return NULL;
    }
    int *res = (int*)malloc(1000 * sizeof(int));
    struct TreeNode **queue = (struct TreeNode**)malloc(1000 * sizeof(struct TreeNode* ));
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    int size = 0;
    while(front < rear){
        size = rear - front;
        for(int i = 0;i<size;i++){
            struct TreeNode *current = queue[front++];
            res[(*returnSize)++] = current->val;
            if(current->left){
                queue[rear++] = current->left;
            }
            if(current->right){
                queue[rear++] = current->right;
            }
        }
    }
    return res;
}

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

0 赞同 0 条回复

花老爷普通 2023年6月30日上午11:18

bfs
时间：O(n)
空间：O(n)

class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            res.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        int[] ans = new int[res.size()];
        int idx = 0;
        for (int temp: res) {
            ans[idx++] = temp;
        }
        return ans;
    }
}

0 赞同 0 条回复

屠龙手段普通 2023年6月29日下午7:15

队列

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        return self.bfs(root)

    def bfs(self, root):
        if not root:
            return []
        queue = [root]
        res = []
        while queue:
            cur_node = queue[0]
            queue = queue[1:]
            res.append(cur_node.val)
            if cur_node.left:
                queue.append(cur_node.left)
            if cur_node.right:
                queue.append(cur_node.right)
        return res

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月29日下午4:27

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

int* levelOrder(struct TreeNode* root, int* returnSize){
    struct TreeNode* Queue[1001];
    int fornt = -1,rear = -1;
    int i = 0;//用来记录数组长度
    int* arr = (int *)malloc(sizeof(int)*1001);

    if(root == NULL){//如果二叉树为空，则直接返回
        (*returnSize) = 0;
        return root;
    }
    Queue[++rear] = root;//根节点先入队
    while(fornt < rear){
        root = Queue[++fornt];//队头元素出队
        arr[i++] = root->val;
        if(root->left != NULL){//如果当前节点有左孩子，那就入队
            Queue[++rear] = root->left;
        }
        if(root->right != NULL){//如果当前节点有右孩子，那就入队
            Queue[++rear]  =root->right;
        }
    }
    *returnSize = i;
    return arr;
}

0 赞同 0 条回复

peach 普通 2023年6月29日上午11:55

思路

使用队列，层序遍历
时间复杂度O(n) 空间复杂度O(n)

代码

 //使用队列，层序遍历
class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> res = new ArrayList();
        if(root == null) return new int[0]; //特殊情况处理，根节点空时addLast报空指针
        Deque<TreeNode> quene = new ArrayDeque();
        quene.addLast(root); //根节点入队
        while(!quene.isEmpty()){
            root = quene.removeFirst(); //弹出根节点
            res.add(root.val);
            if(root.left != null) quene.addLast(root.left); //先左后右
            if(root.right != null) quene.addLast(root.right);   
        }
        return res.stream().mapToInt(Integer::intValue).toArray(); //最后把集合转为数组
    }
}

0 赞同 0 条回复

～普通 2023年6月29日上午11:16

class Solution {
public:
vector levelOrder(TreeNode* root) {
vector res;
queue<TreeNode> q;
if(rootnullptr){
return res;
}
q.push(root);
while(!q.empty()){
TreeNode node = q.front();
q.pop();
res.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
return res;
}
};
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日上午7:24

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        queue<TreeNode*>que;
        vector<int>res;
        if (!root) {
            return res;
        }
        que.push(root);
        while (!que.empty()) {
            TreeNode* curr = que.front();
            que.pop();
            res.push_back(curr->val);
            if (curr->left) {
                que.push(curr->left);
            }
            if (curr->right) {
                que.push(curr->right);
            }
        }
        return res;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月29日上午6:12

记得import

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        if not root:
            return res

        queue = deque([root])

        while queue:

            cnt = len(queue)
            level = []

            for i in range(cnt):
                cur = queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)

            res.append(level)

        return res

0 赞同 0 条回复

江畅普通 2023年6月28日下午11:32

// 层序遍历
// 时间复杂度 O(N)
// 空间复杂度 O(N)
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {

        if (root == nullptr) {
            return {};
        }

        vector<int>      res; // 存储层序遍历节点值
        queue<TreeNode*> que; // 存储层序遍历节点

        // 根节点入队
        que.push(root);

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

            while (size--) {
                // 当前遍历节点
                TreeNode* node = que.front();

                res.push_back(node->val);

                // 当前遍历节点的左节点入队
                if (node->left != nullptr) {
                    que.push(node->left);
                }

                // 当前遍历节点的右节点入队
                if (node->right != nullptr) {
                    que.push(node->right);
                }

                // 当前遍历节点出队
                que.pop();
            }
        }
        return res;
    }
};

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月28日下午8:23

核心思想，拿一个，放两个（该节点的左右节点）
时间复杂度：O(N)
额外空间复杂度：O(N)

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.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                res.add(node.val);
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        int[] resArr = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            resArr[i] = res.get(i);
        }
        return resArr;
    }
}

0 赞同 0 条回复

小吕普通 2023年6月27日下午10:05

c++层序遍历
vector levelOrder(TreeNode* root) {
vectorresult;
queue<TreeNode> que;
if(rootNULL)return result;
que.push(root);
while(!que.empty())
{
TreeNode temp;
int len = que.size();
for(int i = 0;i<len;i++)
{
temp = que.front();
que.pop();
result.push_back(temp->val);
if(temp->left!=NULL)que.push(temp->left);
if(temp->right!=NULL)que.push(temp->right);
}
}
return result;
}

0 赞同 0 条回复

怀瑾永久会员 2023年6月27日下午5:32

C++实现

#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void printFromTopToBottom(TreeNode* root) {
    if (root == NULL) // 判断二叉树是否为空
        return;

    queue<TreeNode*> q; // 定义队列存储节点
    q.push(root); // 将根节点入队

    while (!q.empty()) { // 只要队列不为空就继续循环
        TreeNode* node = q.front(); // 取出队首节点
        q.pop(); // 弹出队首节点
        cout << node->val << " "; // 打印节点值

        // 将左右子节点入队
        if (node->left)
            q.push(node->left);
        if (node->right)
            q.push(node->right);
    }
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    printFromTopToBottom(root); // 打印输出结果

    return 0;
}

0 赞同 0 条回复

彦，，# 普通 2023年6月27日下午5:16

vector<int> levelOrder(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
         /* 定义一个队列用于存储节点的数据 */
        queue<TreeNode*> q;
        if(root != nullptr) q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            for(int i =0;i<n;i++)
            {
                TreeNode* temp = q.front();
                q.pop();
                res.push_back(temp->val);
                if(temp->left != nullptr) q.push(temp->left);
                if(temp->right != nullptr) q.push(temp->right);
            }
        }
        return res;
    }

0 赞同 0 条回复

普通 2023年6月27日下午2:49

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> list = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

利用队列，广搜
时间复杂度O(n)

0 赞同 0 条回复

大鑫啊普通 2023年6月27日下午1:13

时空复杂度：O(n)
1、用队列存储遍历到的节点、用列表顺序保存遍历的结果，用数组进行最后的输出
2、根节点入队，队列非空是循环，将当前节点入列表
3、判断左子树是否为空，不为空则入队，再同样判断右子树

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.offer(t.left);
            if(t.right != null) queue.offer(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 条回复

Vow the vow。普通 2023年6月27日上午11:44

用队列保存边界的上层节点

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

0 赞同 0 条回复

张开怀普通 2023年6月27日上午10:43

/ ** 
  * struct TreeNode{
  *        int val;
  *        TreeNode* left;
  *        TreeNode* right;
  *        TreeNode(int x) : val(x), left(NULL), right(NULL){}
  * } ;
  */

class Solution{
public:
       vector<int> levelOrder(TreeNode* root){
              vector<int> res;
              if(!root){
                     return res;
              }
              queue<TreeNode*> q{{root}};
              while(!q.empty()){
                      auto t = q.front();
                      q.pop();
                      res.push_back(t->val);
                      if(t->left) {
                             q.push(t->left);
                      }
                      if(t->right) {
                             q.push(t->right);
                      }
              }
              return res;
       }
}

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

0 赞同 0 条回复

Jerry 普通 2023年6月26日下午9:57

 //BFS + 队列
class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        ArrayList<Integer> orders = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            orders.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        return orders.stream().mapToInt(Integer::intValue).toArray();
    }
}

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

0 赞同 0 条回复

橙子陈普通 2023年6月26日下午9:34

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

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    List<Integer> res = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode t = queue.poll();
        res.add(t.val);

        if (null != t.left) queue.add(t.left);
        if (null != t.right) queue.add(t.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 条回复

行动派小彩笔普通 2023年6月26日下午8:58

//时间复杂度O(n),空间复杂度O(n),最坏情况，二叉树退化为链表，且有额外的辅助空间
 // 通过队列实现广度优先的层次遍历算法， 从左到右每层的一次入队元素
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> s;
        vector<int> ans;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* tmp = s.front();
            s.pop();
            ans.push_back(tmp->val);
            if(tmp->left) s.push(tmp->left);
            if(tmp->right) s.push(tmp->right);
        }

        return ans;
    }
};

0 赞同 0 条回复

伏月三十普通 2023年6月26日下午8:52

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 时间复杂度O(n)
 空间复杂度O(n)
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null){
            return new int[0];
        }
        LinkedList<TreeNode> queue=new LinkedList<>();
        List<Integer> res=new ArrayList<>();

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

        int[] array=new int[res.size()];
        for(int i=0;i<res.size();i++){
            array[i]=res.get(i);//get(i)得到索引位置上的元素
        }
        return array;
    }
}

0 赞同 0 条回复

yxy 普通 2023年6月26日下午8:45

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        queue<TreeNode*> que;
        que.push(root);
        while(que.size())
        {
            auto cur=que.front();
            que.pop();
            res.push_back(cur->val);
            if(cur->left)
                que.push(cur->left);
            if(cur->right)
                que.push(cur->right);
        }
        return res;
    }
};

复杂度O(n)

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月26日下午6:46

//时间O(n) 空间O(n)
public int[] levelOrder(TreeNode root) {
    if(root == null){
        return new int[]{};
    }

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

    queue.offer(root);

    while(!queue.isEmpty()){
        root = queue.poll();
        result.add(root.val);

        if(root.left != null){
            queue.offer(root.left);
        }
        if(root.right != null){
            queue.offer(root.right);
        }
    }

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

    return res;
}

0 赞同 0 条回复

硬核洋葱普通 2023年6月26日下午6:37

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        queue<TreeNode*> treeque;
        vector<int> ans;
        if(!root)   return ans;
        treeque.push(root);

        while(!treeque.empty()){
            TreeNode* node = treeque.front();
            treeque.pop();
            ans.push_back(node->val);

            if(node->left)
                treeque.push(node->left);
            if(node->right)
                treeque.push(node->right);
        }

        return ans;
    }
};

每遍历到一个节点（出队），就把其左子和右子先后放入队列中，这样最后的效果就是层序遍历
空间复杂度O(n)（一个完全二叉树最后可以有 (n+1)/2 个点在同一层），时间复杂度O(n)

0 赞同 0 条回复

Ming 普通 2023年6月26日下午5:07

复杂度O(height) O(n)

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[]{};
        Queue<TreeNode> q = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            TreeNode node = q.poll();
            list.add(node.val);
            if(node.left != null) {
                q.offer(node.left);
            }
            if(node.right != null) {
                q.offer(node.right);
            }
        }
        int[] array = list.stream().mapToInt(Integer::intValue).toArray();
        return array;
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月26日下午4:32

// c++ 队列
class Solution {
public:
    vector<int> ans;
    vector<int> levelOrder(TreeNode* root) {
        if(!root){
            return ans;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while(!q.empty()){
            int num = q.size();
            while(num--){
                TreeNode* temp = q.front();
                q.pop_front();
                ans.push_back(temp->val);
                if(temp->left) q.push_back(temp->left);
                if(temp->right) q.push_back(temp->right);
            }
        }
        return ans;
    }
};

0 赞同 0 条回复

残月冷骄阳普通 2023年6月26日下午3:48

复杂度

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

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null){
            return new int[0];
        }

        List<Integer> resList = new ArrayList();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            resList.add(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        int[] res = new int[resList.size()];
        for(int i=0; i< resList.size();i++){
            res[i] = resList.get(i);
        }
        return res;
    }
}

0 赞同 0 条回复

雨落圆荷普通 2023年6月26日下午3:09

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;

}

}
时间复杂度：O(n)
额外空间复杂度：容器里最多存放 1/2 的节点，故为 O(n)

0 赞同 0 条回复

Yodl. 普通 2023年6月26日下午2:32


//使用循环队列
class Solution {
public:
    vector levelOrder(TreeNode* root) {
        TreeNode **que = new TreeNode*[1000];
        vector ans;
        if(root==NULL)
        {
            return ans;
        }
        que[0]=root;
        int r=1,f=0;
        while(f!=r)
        {
            TreeNode* tmp;
            tmp=que[f];
            f=(f+1)%1000;
            ans.push_back(tmp->val);
            if(tmp->left!=NULL)
            {
                que[r]=tmp->left;
                r=(r+1)%1000;
            }
            if(tmp->right!=NULL)
            {
                que[r]=tmp->right;
                r=(r+1)%1000;
            }
        }
        return ans;
    }
};
//时间复杂度O(n)
//空间复杂度O(n)

0 赞同 0 条回复

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

共以下 44 个回答

思路：递归

思路

代码

复杂度

Code

# 回答此问题取消回复

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

共以下 44 个回答

思路：递归

思路

代码

复杂度

Code

# 回答此问题 取消回复

# 回答此问题取消回复