leetcode 102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内

• -1000 <= Node.val <= 1000

Related Topics

树

广度优先搜索

二叉树

思路1：队列

分析：按层遍历二叉树，使用队列，遍历每个节点的时候，直接把左右孩子入队即可。但是这道题需要把每一层区分，所以在while中，直接统计这一层的节点数，然后按照节点数出队即可。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
​
        List<List<Integer>> lists = new ArrayList<>();
        if(root == null){
            return lists;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //注意需要把每一层区分开
        while(!queue.isEmpty()){
            //因为每层要单独放 所以要提前统计出这一层的数量 队列前size个都是这一层
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0 ; i < size;i++){
                TreeNode node = queue.poll();
                //遍历这一层 把下一层放入队列中
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
                //统计这一层元素
                list.add(node.val);
            }
            lists.add(list);
        }
        return lists;
    }
}
解答成功:
            执行耗时:1 ms,击败了80.68% 的Java用户
            内存消耗:41.8 MB,击败了5.05% 的Java用户
            

优化：在while循环中创建的list，集合数量固定就是size，可以直接创建长度为size的集合，减少扩容的时间。