剑指Offer32

　　题目描述
　　从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。示例例如：给定二叉树：〔3，9，20，null，null，15，7〕，3920157返回其层次遍历结果：〔〔3〕，〔9，20〕，〔15，7〕〕思路分析
　　与剑指Offer321几乎一摸一样，唯一的区别就是返回的数据格式不同，根据题目要求返回ListListInteger格式。从第一题的分析中已经知道，二叉树按层打印，也就是广度优先搜索BFS，一般需要借助队列的先入先出的性质来实现，但是这一题要求将每一层的数字放在同一个集合List当中，最终返回整个的集合List。这个好办，考虑使用队列，每一层即是当前队列的长度size，但是随着队列不断执行offer操作，队列的大小size是动态改变的。而我们知道的是每层的数字需要被添加到一个临时的temp集合当中，这个集合的大小与队列大小相同，这个简单一个for循环搞定。但是这里需要倒序进行循环，从高到低。因为队列的size不断减小，习惯从低到高遍历结果不正确，但是从高到低，由于初始的size等于每一层结合的大小，递减循环达到条件后直接退出。比采用临时变量方法来得简单一点。思路总结：二叉树为空时的处理借助队列Queue将遍历到的节点存入到队列中，首先入队列的是根节点（root）从左到右，添加子节点（如果存在）对于每一层数字加入到集合当中，采用从高到低的循环添加方式返回结果代码实现classSolution｛publicListListIntegerlevelOrder（TreeNoderoot）｛if（nullroot）｛returnnewArrayList（）；｝QueueTreeNodequeuenewLinkedList（）；ListListIntegerresultnewArrayList（）；queue。offer（root）；while（！queue。isEmpty（））｛ListIntegertempnewArrayList（）；queue的大小是变化的，因此要作为初始值作为遍历的条件for（intiqueue。size（）；i0；i）｛TreeNodenodequeue。poll（）；if（null！node）｛temp。add（node。val）；if（null！node。left）｛queue。offer（node。left）；｝if（null！node。right）｛queue。offer（node。right）；｝｝｝result。add（temp）；｝returnresult；｝｝
　　比较难想到的就是从高到低去循环存入每层的数字，可能平时开发的习惯决定了，遇到for循环这种习惯性从低到高。经验有时候往往也会限制思维的扩展。复杂度
　　时间复杂度O（N）：需要访问二叉树所有节点
　　空间复杂度O（N）：使用队列存储二叉树的节点，极端情况下使用N额外的内存空间链接
　　从上到下打印二叉树II