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

每次只取队列里面原有个数的元素

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        //想办法记录每一层的数量
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> list= new ArrayList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //k记录队列中的元素个数，然后每次只取出k个
            int k = queue.size();
            List<Integer> temp = new ArrayList<>();
            for(int i = 0; i < k; i ++){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            list.add(temp);
        }
        return list;
    }
}

0 赞同 0 条回复

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

注意 root 为 null 的情况

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) return ans;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Queue<TreeNode> t = new LinkedList<>();
            List<Integer> res = new LinkedList<>();
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                res.add(node.val);
                if (node.left != null) t.add(node.left);
                if (node.right != null) t.add(node.right);
            }
            q = t;
            ans.add(res);
        }
        return ans;
    }
}

0 赞同 0 条回复

PatNick 普通 2022年12月21日下午1:23

def levelOrder(self, root: TreeNode):
    if root == None:
        return []
    res =  []
    # 利用队列
    queue = [root]
    while not len(queue)==0:
        cur_list = []
        length = len(queue)
        for _ in range(length):
            cur_list.append(queue[_].val)
            if queue[_].left:
                queue.append(queue[_].left)
            if queue[_].right:
                queue.append(queue[_].right)

        queue = queue[length:]
        res.append(cur_list)

    return res

0 赞同 0 条回复

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

class Solution {
    /**
     * 思路: 本题大致思想仍然与上一题类似，不过需要特别注意的是将每一层打印到一行中。
     * 所以我们可以在每次BFS循环时新建一个临时列表保存每一层的结果，每一层的循环次数为当前队列的长度
     * 复杂度分析:
     * 时间复杂度: T(n) = O(n)   //BFS需要循环n次，n为二叉树的结点数量
     * 空间复杂度: S(n) = O(n)   //最差情况下当树为平衡二叉树时，最多有n/2个树结点同时在queue中，使用O(n)大小的额外空间
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null)
            return list;  //如果树为空，则直接返回空列表[]即可
        Queue<TreeNode> queue = new LinkedList<>();  //如果树不为空，则初始化一个包含跟结点的队列
        queue.add(root);
        while(!queue.isEmpty()){    //对树进行BFS循环，当队列为空时跳出
            List<Integer> tmp = new ArrayList<>();  //新建一个临时列表tmp，用于存储当前层打印的结果
            //这里for循环从高到底，完美避免了后加入的元素进入队列后改变当前循环的次数
            for (int i = queue.size(); i > 0; i--) {    //当前层打印循环: 循环次数为当前层结点数(即队列queue长度)
            //1.首先将队首元素出队，并将其保存到node
            TreeNode node = queue.poll();
            //2.将node.val添加至临时列表tmp中
            tmp.add(node.val);
            //3.添加子节点
            if(node.left != null)
                queue.add(node.left);
            if(node.right != null)
                queue.add(node.right);
            }
            //4.将当前层结果tmp添加到总的集合列表list中
            list.add(tmp);
        }
        //最后将list集合返回即可
        return list;
    }
}

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:53

// 层序遍历+队列
var levelOrder = function(root) {
    if(root == null) {
        return [];
    }
    let queue = [root];
    let res = [];
    while(queue.length) {
        let len = queue.length;
        // 临时数组
        let tmp = [];
        for(let i = 0; i < len; i++) {
            let node = queue.shift();
            tmp.push(node.val);
            node.left &&　queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(tmp);
    }
    return res;
};

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

0 赞同 0 条回复

鸿渐普通 2022年11月16日下午6:20

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
         if(root==null){
            return new ArrayList();
        }
        //存放最后的结果的数组

        List<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            //这题主要的思想是分层思想
            int size = queue.size();
            //当每次从队列当中弹出元素的时候，将元素放在结果集的数组当中
            List<Integer> inner = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                inner.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(inner);
        }
        return res;
    }
}

0 赞同 0 条回复

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

func levelOrder(root *TreeNode) [][]int {
    //定义二维数组
    res := [][]int{}
    if root == nil {
        return nil
    }

    queue := []*TreeNode{root}
    //i代表第i层
    for i := 0; len(queue) > 0; i++ {
        res = append(res, []int{})
        p := []*TreeNode{}
        //将当前层的队列结点打印到一个【】里
        for j := 0; j < len(queue); j++ {
            node := queue[j]
            res[i] = append(res[i], node.Val)
            if node.Left != nil {
            p = append(p, node.Left)
            }
            if node.Right != nil {
            p = append(p, node.Right)
            }
        }
        //将下一层节点队列赋值给queue
        queue = p

    }
    return res
}

O(n)O(n)

0 赞同 0 条回复

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

func levelOrder(root *TreeNode) (res [][]int) {
    //若空树 直接返回
    if root == nil{ 
        return 
    }
    stack := []*TreeNode{} //定义一个队列保存树节点
    stack = append(stack, root)//最开始的时候将根节点加入队列中
    for len(stack) != 0{
        size := len(stack) //求得每一层节点个数
        s := []int{} //用于保存每一层节点的值
        for i:= 0;i < size;i++{//遍历每一层 
            node := stack[0]
            stack = stack[1:]
            if node != nil{
                s = append(s, node.Val) //节点值存入s数组中
                if node.Left != nil{ //若左孩子存在 则入队列
                    stack = append(stack, node.Left)
                }
                if node.Right != nil{//若右孩子存在 则入队列
                    stack = append(stack, node.Right)
                }
            }
        }
        res = append(res, s) //遍历完一层  将该层的结果存入结果集中
    }
    return
}

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

0 赞同 0 条回复

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

因为每行打印完之后需要加一个判断，所以按照原来的出一个入一双的做法，肯定不行，那么就应该需要一个队列来存储出的这些东东。而int的list也需要一个来辅助一下，这样方便一些。

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

需要注意的是：python中的list的appnd方法是浅拷贝，所以不能用 list.clear() 方法在每次append到res之后清空level list，需要让level list重新指向一片空列表区域。

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

0 赞同 0 条回复

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

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

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

0 赞同 0 条回复

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

//时间复杂度 O(N)
//空间复杂度 O(N)
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        //创建一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //创建集合用于收集层次遍历结果
            List<Integer> list = new ArrayList<>();
            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);
            }
            res.add(list);
        }
        return res;
    }
}

0 赞同 0 条回复

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

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = 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 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;
    }
}
时间O(N)空间O(N)

0 赞同 0 条回复

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(null == root){
            return new ArrayList();
        }
        Queue<TreeNode> tmp = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();

        tmp.add(root);

        while(!tmp.isEmpty()){
            List<Integer> tmpAns = new ArrayList<>();
            int levelSize = tmp.size();
            for(int i = 0; i < levelSize; i++){
                TreeNode cur = tmp.poll();
                tmpAns.add(cur.val);
                if(null != cur.left) tmp.add(cur.left);
                if(null != cur.right) tmp.add(cur.right);
            }
            ans.add(tmpAns);
        }
        return ans;

    }
}

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

0 赞同 0 条回复

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

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

class Solution {

    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        Queue que = new LinkedList<>();

        if (root == null)
            return res;

        que.add(root);


        while (!que.isEmpty()) {
            int size = que.size();
            List list = new ArrayList();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                list.add(node.val);

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

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

            res.add(list);
        }

        return res;
    }
}

0 赞同 0 条回复

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

重新定义一个List存每层的元素

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

0 赞同 0 条回复

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

层寻遍历不变，

加上一个变量进行每一层反转

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        vector<vector<int>> res;
        bool list =true;
        while(!que.empty()){ 
            int n = que.size();
            vector<int> vec;
            for(int i = 0;i<n;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);
            }
            if(list){
                list = false;
            }else{
                reverse(vec.begin(),vec.end());
                list = true;
            }
            res.push_back(vec);
        }
        return res;
    }
};

0 赞同 0 条回复

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

修改上一问把每层单独添加元素改为直接添加存放该层val的容器。

class Solution {
public:
    vector<vector<int>> res;
    vector<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);
        }
        res.push_back(nodesVal);
        traverse(nextLevelNodes);
    }  
};

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

0 赞同 0 条回复

lobort 普通 2022年11月1日下午11:52

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();

        //设置总的返回数组
        List<List<Integer>> res = new ArrayList<>();
        queue.offer(root);
        while(!queue.isEmpty()){

            // 设置每一层的数组
            List<Integer> cur = new ArrayList<>();

            //取出每一层的元素
            for(int i = queue.size(); i >0 ;i --){
                TreeNode tmp = queue.poll();
                cur.add(tmp.val);
                if(tmp.left != null){
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){
                    queue.offer(tmp.right);
                }

            }
            //保留每一层的数组
            res.add(cur);
        }
        return res;
    }
}

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

0 赞同 0 条回复

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            tmp = []
            for _ in range(len(stack)):
               node = stack.pop(0)
               tmp.append(node.val)
               if node.left:
                stack.append(node.left)
               if node.right:
                   stack.append(node.right)
            res.append(tmp)
        return res

时间复杂度 O(n)

0 赞同 0 条回复

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

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

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

0 赞同 0 条回复

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

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

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

0 赞同 0 条回复

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

 // 时间、空间复杂度On
 // 利用辅助队列，进行层序遍历
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> dq = new ArrayDeque<>();
        dq.push(root);
        while(!dq.isEmpty()){
            int size = dq.size();
            List<Integer> ans = new ArrayList<>();
            // 遍历一层元素，加入到结果集
            while(size -- > 0){
                TreeNode curr = dq.pollFirst();
                ans.add(curr.val);
                if(curr.left != null){
                    dq.offer(curr.left);
                }
                if(curr.right != null){
                    dq.offer(curr.right);
                }
            }
            res.add(ans);
        }
        return res;
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年10月31日下午10:24

     /**
     * 辅助栈
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
public List> levelOrder(TreeNode root) {
        // 1. 特殊情况
        if (root == null) {
            return new ArrayList<>();
        }

        // 2. 辅助队列用于储存每一层的结点，通过出队实现层序遍历
        List> result = new ArrayList<>();
        Queue queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            // 求队列大小以保证左右孩子都被出队
            int size = queue.size();
            ArrayList temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);

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

0 赞同 0 条回复

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

 /**
     * 剑指 Offer 32 - II. 从上到下打印二叉树 II
     */
    public List<List<Integer>> levelOrders(TreeNode root) {
        //时间复杂度：O(n) 每个节点入队一次
        //空间复杂度 O(n) 最长队列中的元素小于n个
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<>();
            int len = queue.size();
            while (len > 0) {
                TreeNode node = queue.poll();
                if (node != null) {
                    level.add(node.val);
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                len--;
            }
            res.add(level);
        }
        return res;
    }

0 赞同 0 条回复

庄重普通 2022年10月31日下午7:52

//  思路：
//     在从上到下打印二叉树I的基础上，先确定队列的大小，来进行对层的分割
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<int> vec;
        if(root == NULL) return vector<vector<int>>{};

        TreeNode* pNode = root;
        que.push(pNode);
        int n = -1;
        while(!que.empty()){
            n = que.size();

            for(int i = 0; i < n; ++i){
                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();
            }

            vRet.push_back(vec);
            vec.clear();
        }

        return vRet;

    }

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

0 赞同 0 条回复

小肸永久会员 2022年10月31日下午7:02

思路一：BFS。中间需要用一个int变量count记录每一层节点的个数。时间复杂度O(N)，空间复杂度取决于队列中最大存放节点个数。

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

思路二：DFS。时间复杂度O(N)，其中每个节点都被遍历一次，空间复杂度O(N)，递归函数被调用了N次。

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(0, root);
        return res;
    }
    private void dfs(int depth, TreeNode root) {
        if (root == null) {
            return;
        }
        // 如果当前深度等于res的大小，说明当前层是第一次来到，res需要加入一个空的数组来存放这一层的节点值集合
        if (depth == res.size()) {
            res.add(new ArrayList<>());
        }
        res.get(depth).add(root.val);
        dfs(depth + 1, root.left); // 递归+回溯
        dfs(depth + 1, root.right); // 递归+回溯    
    }
}

0 赞同 0 条回复

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

必须包含中文
    public List<List<Integer>> level(TreeNode root){
        if (root==null) return new ArrayList<>();

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

        queue.add(root);
        while (!queue.isEmpty()){
            int k=queue.size();
            List<Integer> tmp=new ArrayList<>();
            for (int i = 0; i < k; i++) {
                TreeNode t=queue.poll();
                tmp.add(t.val);
                if (t.left!=null)queue.add(t.left);
                if (t.right!=null) queue.add(t.right);
            }
            res.add(tmp);
        }

        return res;
    }

0 赞同 0 条回复

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

下面代码

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

0 赞同 0 条回复

y 普通 2022年10月31日下午3:21

//  层序遍历
var levelOrder = function(root) {
  if(!root) return [];
  let res = [];
  let queue = [root];
  while(queue.length) {
      let n = queue.length;
      //保存每层节点
      let cur = [];
      for(let i = 0;i < n;i++) {
          let node = queue.shift();
          cur.push(node.val);
          node.left && queue.push(node.left);
          node.right && queue.push(node.right);
      }
      res.push(cur);
  }
  return res;
};

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

0 赞同 0 条回复

mpweixin用户普通 2022年10月31日下午2:29

“`c++
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> result;
queue queue;
if (!root) return result;
queue.push(root);

    // vector<int> res;
    while (!queue.empty()) {
        vector<int> res;   // 半天意识不到是这里的问题：看了答案才反应过来为什么我写出来是那个样子因为一直是在原有的基础上继续创建链表。但实际是要每次都使用新的才对！
        int size = queue.size();
       while (size--) {
            TreeNode* node = queue.front();       
            queue.pop();     
            res.push_back(node->val);                

            if (node->left) queue.push(node->left);
            if (node->right) queue.push(node->right);
       }
        result.push_back(res);            
    }

    return result;
}

};

“`

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月31日下午1:49

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

        if(root == null)  return res;

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

        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            for(int i=queue.size();i>0;i--){

                 TreeNode q = queue.poll();
                 list.add(q.val);
                 if(q.left != null) queue.add(q.left);
                 if(q.right != null) queue.add(q.right);

             }
             res.add(list);
    }
    return res;
    }
}

时间复杂度O(n)
空间复杂度O(n)
1.一层的拿一个数组来集合出来，就用for(int i=queue.size();i>0;i–){}

0 赞同 0 条回复

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

解题思路：
1、按层打印：题目要求的二叉树的从上至下打印（即按层打印），又称为二叉树的广度优先搜索（BFS）。BFS 通常借助队列的先入先出特性来实现。

2、每层打印到一行：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

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

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = 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 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 条回复

阿白普通 2022年10月31日下午12:27

从根开始，把下一层子树遍历完，把再下一层的子树存到队列，如此往复，直到最后一层没有子树、导致队列为空，退出
时间O（n），空间O（n）

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

    }
};

0 赞同 0 条回复

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

//递归
class Solution {
public:
vector<vector> res;
void fun(TreeNode* root,int num){
if(!root) return;
if(numres.size()) res.push_back(vector{});
res[num].push_back(root->val);
fun(root->left,num+1);
fun(root->right,num+1);
return;
}
vector<vector> levelOrder(TreeNode* root) {
fun(root,0);
return res;

};

0 赞同 0 条回复

易水寒永久会员 2022年10月31日上午11:20

记录每层长度

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

0 赞同 0 条回复

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

定义队列和集合，队列存放节点，先是while循环，然后内部for遍历完树的某一层，并且添加新的左右节点到队列中，每次for循环完,添加数据到集合list中
时间O(n)
空间O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        if(root == null)    return res;

        que.add(root);
        while(!que.isEmpty()){
            int len = que.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0;i<len;i++){

                TreeNode pre = que.poll();
                list.add(pre.val);
                if(pre.left!=null)  que.add(pre.left);
                if(pre.right!=null) que.add(pre.right);
            }
            res.add(list);
        }
        return res;
    }
}

0 赞同 0 条回复

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

时间空间复杂度为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 List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            //关键就是设置这个每层的个数，也就是队列个数，队列个数就是每层的个数
            int k = queue.size();
            List<Integer> list1 = new ArrayList<>();
        for(int i=0;i<k;i++){
            TreeNode node = queue.poll();
            list1.add(node.val);
            if(node.left !=null) queue.add(node.left);
            if(node.right !=null) queue.add(node.right);
            }
           list.add(list1);
        }
        return list;
    }
}

0 赞同 0 条回复

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

class Solution {
//使用两个队列来进行遍历，两个队列分别装载每一层
//时间复杂度O(n)
//空间复杂度O(n)
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        TreeNode temp = root;
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.add(root);
        List<List<Integer>> lists = new ArrayList<>();
        while (!queue1.isEmpty()||!queue2.isEmpty()) {
            List<Integer> nodes = new ArrayList<>();
            if(queue2.isEmpty()) {
                while (!queue1.isEmpty()) {
                    TreeNode node = queue1.remove();
                    nodes.add(node.val);
                    if (node.left != null) queue2.add(node.left);
                    if (node.right != null) queue2.add(node.right);
                }
                lists.add(nodes);
            }else if(queue1.isEmpty()){
                while (!queue2.isEmpty()) {
                    TreeNode node = queue2.remove();
                    nodes.add(node.val);
                    if (node.left != null) queue1.add(node.left);
                    if (node.right != null) queue1.add(node.right);
                }
                lists.add(nodes);
            }
        }

        return lists;
    }
}

0 赞同 0 条回复

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

时间复杂度O(n) 空间复杂度 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 List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        //同理操作，只是返回值不一样，原理基本是相同的
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();

        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            List<Integer> temp = new ArrayList<>();
            for(int i = 0;i < k;i++){
               TreeNode t1 = queue.poll();
               temp.add(t1.val);
               if(t1.left!=null) queue.add(t1.left);
               if(t1.right!=null) queue.add(t1.right);
            }
            res.add(temp);
        }

        return res;

    }
}

0 赞同 0 条回复

云雾里普通 2022年10月31日上午7:55

class Solution {
    //DFS一层一层保存
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root==null)return result;
        List<TreeNode> list = new ArrayList<>(){{add(root);}},tmp;
        while (!list.isEmpty()){
            tmp=new ArrayList<>();
            List<Integer> resultSon = new ArrayList<>();
            for (TreeNode treeNode : list) {
                resultSon.add(treeNode.val);
                if(treeNode.left!=null){
                    tmp.add(treeNode.left);
                }
                if(treeNode.right!=null){
                    tmp.add(treeNode.right);
                }
            }
            list=tmp;
            result.add(resultSon);
        }
        return result;
    }

    /*public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }*/
}

0 赞同 0 条回复

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

/**
    怎么感觉就是我上一个题的写法....
    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null) return new ArrayList<List<Integer>>();
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        ArrayList<Integer> layer = new ArrayList<>();
        ArrayList<List<Integer>> ans = new ArrayList<>();
        TreeNode p = root;
        q1.offer(root);
        while(!q1.isEmpty()){
            while(!q1.isEmpty()){
                p = q1.poll();
                layer.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>();
            ans.add(layer);
            layer = new ArrayList<>();
        }

        return ans;
    }
}

0 赞同 0 条回复

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

解题思路：同样借助队列使用广度优先遍历二叉树，同时对于每一层节点嵌套进行循环遍历，将每一层的节点值加入一个列表中，单层循环结束后再加入result列表中。
时间复杂度：O(n)，每个节点进出队列一次
空间复杂度：O(n),队列中最多节点数量为n/2个

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res = []
        queue = [root]
        while queue:
            # 存储当前层的所有节点的值
            sub_res = []
            # 循环当前层节点数量次
            for i in range(len(queue)):
                cur_node = queue.pop(0)
                sub_res.append(cur_node.val)
                if cur_node.left:
                    queue.append(cur_node.left)
                if cur_node.right:
                    queue.append(cur_node.right)
            res.append(sub_res)
        return res

0 赞同 0 条回复

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

思路还是迭代，和上一个题的区别，就是子树需要额外的一个链表去存起来，然后再添加到返回列表里面时间复杂度O(n),空间复杂度O(2n)

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

        return res

0 赞同 0 条回复

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

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

        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){ 
            vector<int> tmp;
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                if(front->left) q.push(front->left);
                if(front->right) q.push(front->right);
            }
            ret.push_back(tmp);

        }
        return ret;
    }
};

注意在内层队列赋值的循环中，不能直接将循环的判断条件写成queue.size(),因为在每次循环内部queue的容量发生了变化

0 赞同 0 条回复

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int k = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < k; i++) {
                TreeNode t = queue.poll();
                tmp.add(t.val);
                if (t.left != null) {
                    queue.add(t.left);
                }
                if (t.right != null) {
                    queue.add(t.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }
}

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

0 赞同 0 条回复

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

利用队列层次遍历

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

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

递归

/**
递归
时间复杂度O(N) 空间复杂度O(N)
 */
class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
       bfs(root,0);
       return ret;
    }
    public void bfs(TreeNode root,int depth){
        if(root != null){
            if(ret.size() <= depth) ret.add(new ArrayList());//给每一层添加list
            ret.get(depth).add(root.val);
            bfs(root.left,depth+1);
            bfs(root.right,depth+1);
        }
    }
}

0 赞同 0 条回复

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

和上一题思路差不多，只不过这次利用一个for循环让每一行树节点分别输出到一个数组中
时间复杂度O(n) 空间复杂度O(n)

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vec1;

        queue<TreeNode*> que;
        if(root == NULL) return vec1;

        que.push(root);
        while(!que.empty()){
            vector<int> vec2;
            int k = que.size();
            for(int i = 0;i < k;i++){
                TreeNode* tmp = que.front();
                vec2.push_back(tmp->val);
                que.pop();
                if(tmp->left != NULL) que.push(tmp->left);
                if(tmp->right != NULL) que.push(tmp->right);
            }
            vec1.push_back(vec2);
        }
        return vec1;
    }
};

0 赞同 0 条回复

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

共以下 48 个回答

注意 root 为 null 的情况

层寻遍历不变，

加上一个变量进行每一层反转

# 回答此问题取消回复

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

共以下 48 个回答

注意 root 为 null 的情况

层寻遍历不变，

加上一个变量进行每一层反转

# 回答此问题 取消回复

# 回答此问题取消回复