宁永久会员 2023年3月10日下午3:22

注意子节点不为空才能添加进去

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

0 赞同 0 条回复

lucca 普通 2023年1月4日下午3:15

时间复杂度O(N) BFS

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

        Queue<Integer> v = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode p = q.poll();
            v.add(p.val);
            if (p.left != null) q.add(p.left);
            if (p.right != null) q.add(p.right);
        }

        int[] ans = new int[v.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = v.poll();
        }
        return ans;
    }
}

0 赞同 0 条回复

PatNick 普通 2022年12月21日上午10:56

# 需要指针
def levelOrder(root: TreeNode):
    arr = [root]
    res = [root.val]
    # 指针，指针从左往右遍历list
    point = 0
    while not point > len(arr)-1:
        if arr[point].left:
            arr.append(arr[point].left)
            res.append(arr[point].left.val)
        if arr[point].right:
            arr.append(arr[point].right)
            res.append(arr[point].right.val)
        point += 1

    return res

0 赞同 0 条回复

如梦似歌普通 2022年12月18日下午3:52

class Solution {
    public int[] levelOrder(TreeNode root) {
        /**
         * 使用非递归(队列)的方法实现
         * 复杂度分析:
         * 时间复杂度: T(n) = O(n)   //BFS需要循环n次，n为二叉树的结点数量
         * 空间复杂度: S(n) = O(n)   //最差情况下当树为平衡二叉树时，最多有n/2个树结点同时在queue中，使用O(n)大小的额外空间
         */
        if(root == null)
            return new int[0];  //当树的根结点为空时，直接返回空列表[]即可
        Queue<TreeNode> queue = new LinkedList<>();  //初始化一个包含根结点的队列
        queue.add(root);
        ArrayList<Integer> list = new ArrayList<>(); //初始化一个list集合，用来保存每一次出队的元素的值
        //对树进行BFS循环,当队列queue为空时跳出循环,否则继续循环
        while(!queue.isEmpty()){
            //poll 移除并返问队列头部的元素 如果队列为空，则返回null
            TreeNode node = queue.poll();   //首先将队首元素出队，并存入到node结点中
            list.add(node.val);     //将node.val添加至list集合中
            //若node的左(右)子结点不为空，则将左(右)子结点加入队列queue中
            if(node.left != null)
                queue.add(node.left);
            if(node.right != null)
                queue.add(node.right);
        }
        int[] res = new int[list.size()];  //初始化一个数组res，其长度为list集合的长度，用于保存list集合中的所有元素
        for (int i = 0; i < list.size(); i++) {   //逐一将list集合中的元素复制到数组res中
            res[i] = list.get(i);
        }
//      //一步转换写法
//      int[] res = list.stream().mapToInt(Integer::valueOf).toArray();
        return res;  //最后返回打印结果列表res即可

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:13

class Solution {
public: //层序遍历即可
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==nullptr) return res;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0; i < size;i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            res.push_back(vec);
        }
        return res;
    }
};

0 赞同 0 条回复

cute. 普通 2022年11月19日上午9:33

 // 该题目使用队列进行求解，先进先出原则
var levelOrder = function(root) {
    // 判断头结点是否为空，为空则创建一个空数组
    if(root == null) {
        return [];
    }
    // 辅助队列
    // 默认将头结点加入到队列中
    let queue = [root];
    // 数组存取结果
    let res = [];
    // 循环队列
    while(queue.length) {
        // 将队列最上面拿出来
        // shift() 方法用于把数组的第一个元素从其中删除,并返回第一个元素的值
        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;
};

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

0 赞同 0 条回复

鸿渐普通 2022年11月16日下午5:08

class Solution {
    public int[] levelOrder(TreeNode root) {
            if(root==null){
            return new int[0];
        }
        //存放最后的结果的数组
        List<Integer> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        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()];
        for (int i = 0; i < res.size(); i++) {
            ans[i]=res.get(i);
        }
        return ans;
    }
}

0 赞同 0 条回复

xye 普通 2022年11月16日上午10:38

func levelOrder(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    res := []int{}
    queue := []*TreeNode{root}
    for len(queue) != 0 {
        t := queue[0]
        res = append(res, t.Val)
        if t.Left != nil {
            queue = append(queue, t.Left)
        }
        if t.Right != nil {
            queue = append(queue, t.Right)
        }
        queue = queue[1:]

    }
    return res

}

时间O(n)空间O(n)

0 赞同 0 条回复

symbol 普通 2022年11月9日下午7:20

func levelOrder(root *TreeNode) (res []int) {
    stack := []*TreeNode{} //定义一个队列用来保存树节点
    stack = append(stack, root)
    for len(stack) != 0{ //队列不为空就一直弹出
        node := stack[0]
        stack = stack[1:]
        if node != nil{
            res = append(res, node.Val) // 出队列就保存进入结果集
            if node.Left != nil{//存在左孩子 则左孩子如队列
                stack = append(stack, node.Left)
            }
            if node.Right != nil{//存在右孩子 则右孩子入队列
                stack = append(stack, node.Right)
            }
        }
    }
    return
}

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

0 赞同 0 条回复

黎昕普通 2022年11月6日下午9:16

因为C语言写这个东西太难写了，所以最近学了python3来写这些题目
collections模块是一个双端队列，可以用于模拟栈队列等等数据结构，很好用，python真的是太简便太好用了

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:return []
        res,queue=[],collections.deque()
        queue.append(root)
        while queue:
            node=queue.popleft()
            res.append(node.val)
            if node.left:queue.append(node.left)
            if node.right:queue.append(node.right)
        return res

0 赞同 0 条回复

刺猬普通 2022年11月5日下午4:54

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

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

0 赞同 0 条回复

感到自己好渺小普通 2022年11月5日上午12:12

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
    //层次遍历，广度优先搜索
    //思路
    //利用队列来实现BFS ，如果树的根节点不为空，先将根节点放入队列当中，将根节点出队，再将与根节点相连的左右结点入队，然后再将左节点出队，将与左节点相连的结点入队，直到队列为空，遍历完成
    //对二叉树的层次遍历其实是通过队列中队首元素的不断出队来实现的，直到队列为空，遍历完成
        public int[] levelOrder(TreeNode root) {
        //首先判断根节点是否为空，如果为空，则返回一个空数组
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        //先将根节点加入到队列中
        queue.add(root);
        while(!queue.isEmpty()){
            //node记录队首元素
            TreeNode node = queue.poll();
            ans.add(node.val);
            //如果node的左节点不为空，将node 的左节点加入到队列中
            if(node.left!=null) queue.add(node.left);
            //如果node的右节点不为空，将node 的右节点加入到队列中
            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;
    }
}

0 赞同 0 条回复

浅夏的无奈普通 2022年11月4日下午10:26

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
    public int[] levelOrder(TreeNode root) {
        //判断头节点是否为空
        if(root == null) return new int[0];
        Queue<TreeNode> queue= new LinkedList<>();
        queue.add(root);
        ArrayList<Integer> arr=new ArrayList<>();
        //循环遍历二叉树
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            arr.add(node.val);
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
        }
        int[] res = new int[arr.size()];

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

0 赞同 0 条回复

lobort 普通 2022年11月4日下午9:58

class Solution {
    public int[] levelOrder(TreeNode root) {
        //判断特殊情况
        if(root == null ){
            return new int[0];
        }
        //新建一个队列存放
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        ArrayList<Integer> ans = new ArrayList<>();
        queue.offer(root);
        // while(queue !=null)
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            ans.add(cur.val);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        int [] res = new int[ans.size()];
        for(int i = 0; i<ans.size();i++){
            res[i] = ans.get(i);
        }
        return res; 
    }
}

0 赞同 0 条回复

星河普通 2022年11月4日下午4:06

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        ArrayList<Integer> 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);
        }
        //arraylist转int[]
        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 条回复

酥合普通 2022年11月3日下午10:51

/**
 * 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(null == root){
            return new int[0];
        }
        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> tmp = new LinkedList<>();
        tmp.add(root);
        while (!tmp.isEmpty()){
            TreeNode cur = tmp.poll();
            if (cur.left != null){
                tmp.add(cur.left);
            }
            if(cur.right != null){
                tmp.add(cur.right);
            }
            ans.add(cur.val);
        }
        int[] ansa = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            ansa[i] = ans.get(i);
        }
        return ansa;

    }
}

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

0 赞同 0 条回复

@ 普通 2022年11月3日下午4:09

思路：使用辅助队列
时间复杂度 O(N)： NNN 为二叉树的节点数量，即BFS需循环N次。
空间复杂度 O(N) ：最差情况下，即当树为平衡二叉树时，最多有 N/2个树节点同时在 queue 中，使用 O(N)大小的额外空间。

class Solution {
    public int[] levelOrder(TreeNode root) {
         List<Integer> res = new ArrayList<Integer>();

        if(root == null)
            return res.stream().mapToInt(Integer::valueOf).toArray();

        Queue<TreeNode> que = new LinkedList<>();

        que.add(root);

        while(!que.isEmpty()){
            TreeNode node = que.remove();
            res.add(node.val);

            if(node.left != null)
                que.add(node.left);

            if(node.right != null)
                que.add(node.right);

        }

        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
}

0 赞同 0 条回复

一只骆驼普通 2022年11月3日下午2:17

层序遍历，用一个队列来存放节点，最后从list转为int[]，试了一下用stream去转，发现效率还不如遍历

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

0 赞同 0 条回复

狗蛋儿普通 2022年11月2日下午9:00

层序遍历

需要使用一个堆，来暂时存放一层节点

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

0 赞同 0 条回复

cxxz 普通 2022年11月2日下午1:15

通过两个前序遍历，一个获取下一层的节点所以，另一个添加该层的值到 result 中。

class Solution {
public:
    vector<int> res;
    vector<int> levelOrder(TreeNode* root) {
        if (root == NULL)
             return res;
        vector<TreeNode *> nodes;
        nodes.push_back(root);
        traverse(nodes);
        return res;
    }

    void traverse(vector<TreeNode *> &curLevelNodes) {
        // base
        if (curLevelNodes.empty())
            return;
        vector<int> nodesVal;
        vector<TreeNode *> nextLevelNodes;
        // preorder 添加值和获取下一层节点
        for (auto node : curLevelNodes) {
            nodesVal.push_back(node->val);
            if (node->left != NULL)
                nextLevelNodes.push_back(node->left);
            if (node->right != NULL)
                nextLevelNodes.push_back(node->right);
        }
        for (auto val : nodesVal)
            res.push_back(val);
        traverse(nextLevelNodes);
    }  
};

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

0 赞同 0 条回复

云雾里普通 2022年11月2日上午11:02

//层级遍历
class Solution {
    public int[] levelOrder(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if(root==null)return new int[0];
        List<TreeNode> list = new ArrayList<>(){{add(root);}},tmp;
        while (!list.isEmpty()){
            tmp=new ArrayList<>();
            for (TreeNode treeNode : list) {
                result.add(treeNode.val);
                if(treeNode.left!=null){
                    tmp.add(treeNode.left);
                }
                if(treeNode.right!=null){
                    tmp.add(treeNode.right);
                }
            }
            list=tmp;
        }
       return result.stream().mapToInt(Integer::intValue).toArray();
    }
    /*public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }*/
}

0 赞同 0 条回复

Error 普通 2022年11月1日下午9:34

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        s = []
        stack = [root]
        while stack:
            v = stack.pop(0)
            s.append(v.val)
            if v.left:
                stack.append(v.left)
            if v.right:
                stack.append(v.right)
        return s

时间复杂度 O(n)

0 赞同 0 条回复

Whatever 永久会员 2022年11月1日下午3:05

使用层序遍历，时间O(n)，空间O(n)

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

0 赞同 0 条回复

Y7n05h 普通 2022年11月1日下午1:17

class Solution {
public:
    vector<int> levelOrder(TreeNode *root) {
        vector<int> res;
        if (!root) return res;
        deque<TreeNode *> buf{root};
        while (!buf.empty()) {
            auto *tmp = buf.front();
            if (tmp->left) buf.push_back(tmp->left);
            if (tmp->right) buf.push_back(tmp->right);
            res.push_back(tmp->val);
            buf.pop_front();
        }
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(1) （返回值不计入空间复杂度）

0 赞同 0 条回复

Tolkien 永久会员 2022年11月1日上午9:49

/**
     * 辅助队列
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public int[] levelOrder(TreeNode root) {
        // 1. 特殊情况
        if (root == null) {
            return new int[]{};
        }

        // 2. 使用辅助队列储存每个节点的左右孩子，通过出队来实层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        LinkedList<Integer> resultList = new LinkedList<>();


        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            resultList.add(node.val);

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

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

        return result;
    }

0 赞同 0 条回复

优秀市民普通 2022年11月1日上午12:25

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

        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[] result = new int[res.size()];

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

    }
}

时间复杂度on

0 赞同 0 条回复

Gg 普通 2022年10月31日下午11:40

 // 时间复杂度，遍历树On
 // 空间复杂度，容器保存一半的元素 On
class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null){
            return new int[0];
        }
        Deque<TreeNode> dq = new ArrayDeque<>();
        dq.offer(root);
        while(!dq.isEmpty()){
            int size = dq.size();
            while(size -- > 0){
                TreeNode curr = dq.pollFirst();
                res.add(curr.val);
                if(curr.left != null){
                    dq.offer(curr.left);
                }
                if(curr.right != null){
                    dq.offer(curr.right);
                }
            }
        }
        int[] resInt = new int[res.size()];
        for (int j = 0; j < res.size(); j++) {
            resInt[j] = res.get(j);
        }

        return resInt;
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年10月31日下午9:17

/**
     * 剑指 Offer 32 - I. 从上到下打印二叉树
     *
     * @return
     */
    public int[] levelOrder(TreeNode root) {
        //层序遍历
        //时间复杂度O(n) n是树的节点数
        //空间复杂度O(n) 最大的空间是满二叉树的时候使用n/2 所有空间复杂度是n
        if (root == null) return new int[0];
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            while (len > 0) {
                TreeNode node = queue.poll();
                if (node != null) {
                    res.add(node.val);
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                len--;
            }
        }
        int[] array = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            array[i] = res.get(i);
        }
        return array;
    }

0 赞同 0 条回复

庄重普通 2022年10月31日下午5:58

//  思路：
//     1.利用队列辅助完成从上到下同一层的节点按照从左到右的顺序打印
//     2.把根节点的左右节点依次push进队列,front获取的值即为同层的所有节点顺序
//     3.进行循环即可
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        if(root == NULL) return vector<int>{};

        que.push(root);
        TreeNode* pNode = NULL;
        while(!que.empty()){
            pNode = que.front();
            vec.push_back(pNode->val);

            if(pNode->left != NULL)
                que.push(pNode->left);

            if(pNode->right != NULL)
                que.push(pNode->right);

            que.pop();
        }
        return vec;
    }

    queue<TreeNode*> que; 
    vector<int> vec;
};
//时间复杂度O(n)
//空间复杂度O(n)

0 赞同 0 条回复

马啸天永久会员 2022年10月31日下午4:38

    public List<List<Integer>> levelOrder(TreeNode root) {

        if (root == null) return new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        int sum = 1;
        queue.add(root);
        while (!queue.isEmpty()) {

            int k = queue.size();
            LinkedList<Integer> tmp = new LinkedList<>();
            for (int i = 0; i < k; i++) {
                TreeNode t = queue.poll();
                if (sum % 2 == 1) {
                    tmp.add(t.val);
                } else {
                    tmp.addFirst(t.val);
                }

                if (t.left != null) queue.add(t.left);
                if (t.right != null) queue.add(t.right);
            }
            res.add(tmp);
            sum++;
        }

        return res;
    }
必须含有中文

0 赞同 0 条回复

T 普通 2022年10月31日下午4:29

下面代码

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

0 赞同 0 条回复

小肸永久会员 2022年10月31日下午4:07

思路：广度优先搜索，用一个队列，先把根节点加入到队列中，从队列取出一个节点加入到结果集中，再看它的左右子节点是否为空，不为空，就加入到队列中，不断循环，直到队列为空，因为队列是先入先出，所以这样结果集中节点的顺序就是层次遍历的顺序了。时间复杂度O(N)，空间复杂度取决于队列中最多存放的那一次节点个数。

class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return new int[0];
        }
        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);
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();    
    }
}

0 赞同 0 条回复

wxc 普通 2022年10月31日下午3:49

队列

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

        res, q = [], collections.deque()
        q.append(root)

        while q:
            node = q.popleft()
            res.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return res

0 赞同 0 条回复

y 普通 2022年10月31日下午2:46

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

队列

0 赞同 0 条回复

绍熙普通 2022年10月31日下午1:39

解题思路：
借助队列的先入先出特性来实现

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};
        ArrayList<Integer> 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;
    }
}

0 赞同 0 条回复

just 普通 2022年10月31日下午12:17

//队列
class Solution {
public:

vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    queue<TreeNode*> que;
    if(!root) return res;
    que.push(root);
    while(!que.empty()){
        int size=que.size();
        for(int i=0;i<size;++i){
            TreeNode* 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;

}

};

0 赞同 0 条回复

是梦终空永久会员 2022年10月31日上午10:33

定义队列存放树的各个节点，list集合存放val，由于队列先进先出，所以循环遍历，挨个添加TreeNode，最后将list的val存入数组
时间O(n)
空间O(n)

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null)     return new int[0];
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        List<Integer> list = new ArrayList<>();
        while(!que.isEmpty()){
            TreeNode pre = que.poll();
            list.add(pre.val);
            if(pre.left!=null)  que.add(pre.left);
            if(pre.right!=null) que.add(pre.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用户永久会员 2022年10月31日上午10:12

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

空间时间复杂度均为O（n)

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月31日上午10:09

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

/**
 * 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];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        queue.add(root);
        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[] arr = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            arr[i] = list.get(i);
        }
        return arr;
    }
}

0 赞同 0 条回复

派大星普通 2022年10月31日上午9:42

class Solution {
//使用队列来接收遍历到的二叉树节点，然后把队列中的数据拿出来，放入一个数组中
//时间复杂度O(n)
//空间复杂度O(n)
    public int[] levelOrder(TreeNode root) {
            if(root==null){
                return new int[0];
            }
            List<Integer> nodes = new ArrayList<>();
            TreeNode temp = root;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);

                while (!queue.isEmpty()) {
                    TreeNode node = queue.remove();
                    nodes.add(node.val);
                    if(node.left!=null) queue.add(node.left);
                    if(node.right!=null) queue.add(node.right);
                }

            int[] values = nodes.stream().mapToInt(Integer::intValue).toArray();
                return values;

        }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年10月31日上午8:36

解题思路：从上层至下层打印，二叉树广度优先搜索，借用队列先入先出的特性来实现。初始化一个集合用于存放二叉树结点的val值，最后将值在循环条件存入数组，最后将数组的值返回

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 vals = queue.poll(); //队列最上面的数拿出来
            res.add(vals.val);
            if(vals.left!=null) queue.add(vals.left);
            if(vals.right!=null) queue.add(vals.right);
        }
        int [] arr = new int [res.size()];
        for(int i = 0;i<res.size();i++){
            arr[i] = res.get(i);
        }
        return arr;
    }
}

0 赞同 0 条回复

阿白普通 2022年10月31日上午7:06

1、从根节点开始，将子树放在队列，从左到右遍历一层子树同时将下一层子树依次入队
2、时间O（n），空间O（n）

class Solution {
public:
    std::vector<int> levelOrder(TreeNode* root) {
        if (root == nullptr)
            return{};

        std::vector<int> res;
        std::queue<TreeNode*> temp;

        temp.push(root);
        while (!temp.empty())
        {
            TreeNode *tree = temp.front();
            res.push_back(tree->val);
            if (tree->left != nullptr)
                temp.push(tree->left);
            if (tree->right != nullptr)
                temp.push(tree->right);

            temp.pop();
        }
        return std::move(res);

    }
};

0 赞同 0 条回复

青木普通 2022年10月30日下午11:48

/**
    没转过弯，还以为要一层一层输出，多设置了一个队列....
    时间复杂度O(n);
    空间复杂度O(n)
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null) return new int[0];
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        ArrayList<Integer> ans = new ArrayList<>();
        TreeNode p = root;
        q1.offer(root);
        while(!q1.isEmpty()){
            while(!q1.isEmpty()){
                p = q1.poll();
                ans.add(p.val);
                if(p.left!=null) q2.offer(p.left);
                if(p.right!=null) q2.offer(p.right);
            }
            q1 = q2;
            q2 = new LinkedList<TreeNode>();
        }

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

        return res;

    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月30日下午11:10

解题思路：借助队列使用广度优先方法对二叉树进行遍历
时间复杂度：O(n)
空间复杂度：O(n)，最差情况，平衡二叉树时，有n/2个节点位于队列中

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        res = []
        if not root:
            return []
        queue = [root]
        while queue:
            cur_node = queue.pop(0)
            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 条回复

天然普通 2022年10月30日下午10:49

改良迭代求深度的方法，把每次迭代的值记录下来，然后返回时间复杂度O(n),空间复杂度O(n)

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root: return []
        num = [root]
        res = [root.val]
        while num:
            k = []
            for i in num:
                if i.left: 
                    k.append(i.left)
                    res.append(i.left.val)
                if i.right:
                    k.append(i.right)
                    res.append(i.right.val)
            num = k


        return res

0 赞同 0 条回复

追普通 2022年10月30日下午10:00

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ret;
        if(root == nullptr) return ret;

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            TreeNode* front = q.front();
            q.pop();
            if(front->left) q.push(front->left);
            if(front->right) q.push(front->right);
            ret.push_back(front->val);
        }
        return ret;
    }
};

广度优先搜索（BFS）通常借助队列先进先出的的特性来实现

0 赞同 0 条回复

So 普通 2022年10月30日下午8:54

/**
 * 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];
        }
        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)，空间：O(n)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月30日下午8:29

时间复杂度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> list = new ArrayList<>();
        queue.offer(root);
        list.add(root.val);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode cur = queue.poll();
                if(cur.left != null) {queue.offer(cur.left);
                list.add(cur.left.val);}
                if(cur.right != null){ queue.offer(cur.right);
                list.add(cur.right.val);}
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月30日下午6:43

1、从上到下打印二叉树用队列来解决，定义一个存放树节点的队列
2、先将树的根节点存入队列中，当队列不为空时，将队列中的队首元素取出，并将其值存入到vector中，同时将该节点的左右子节点存入到队列中
3、时间复杂度O(n) 空间复杂度O(n)

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

0 赞同 0 条回复

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

共以下 49 个回答

时间复杂度O(N) BFS

层序遍历

需要使用一个堆，来暂时存放一层节点

# 回答此问题取消回复

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

共以下 49 个回答

时间复杂度O(N) BFS

层序遍历

需要使用一个堆，来暂时存放一层节点

# 回答此问题 取消回复

# 回答此问题取消回复