题目概述(中等难度)
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
返回其层序遍历结果：
[ [3], [9,20], [15,7] ]
题目链接：
思路与代码
思路展现
这道题目的核心其实就是怎么把每层的元素单独 存入一个list当中去，所以此处我们引入了size这个变量，用于记录每层元素的个数，每当我们向list中存入一层当中的一个元素的时候，size就减1.
代码示例
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<>(); if(root == null) { //此时没有元素，返回值为null return ret; } Queue<TreeNode> queue = new LinkedList<>(); //先把二叉树根节点放入我们的队列中 queue.offer(root); while(!queue.isEmpty()) { //每一个新的list用于存放每层的元素 List<Integer> list = new ArrayList<>(); //size用于记录每层的元素个数 int size = queue.size(); while(size > 0) { TreeNode cur = queue.poll(); list.add(cur.val); if(cur.left != null) { queue.offer(cur.left); } if(cur.right != null) { queue.offer(cur.right); } //注意size每次要递减 size--; } ret.add(list); } return ret; } }
对于代码不懂可以画下图分析下，就懂了.
总结
考察对于层序遍历的掌握
记树上所有节点的个数为 n。
时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。
