P102

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]

这题其实就是说的对树的广度优先遍历,常见的方法就是用队列,先把3,压入队列,然后弹出时,输出3,再将其左右子节点压入,这题目需要将同一层级放到同一个list里,以3为例,3弹出后,队列为空,压入9,20再进入的时候其实已经知道此时在队列的数据都是同一层级的,所以按照队列大小遍历即可

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null){
            return lists;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            //此时队列的数据都是同一层级
            for (int i =0;i<size;i++){
                TreeNode node = queue.poll();
                list.add(node.val);
              //压入左右子节点
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            lists.add(list);
        }


        return lists;
    }