102. 二叉树的层次遍历

题目描述

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如: 给定二叉树: [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回其层次遍历结果：

[ [3], [9,20], [15,7] ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的思路

采用队列可实现题目要求。 先把根结点加入队列，然后每循环一次取出当前层的一个结点（直到把当前层的结点全部取出来为止，利用thisCount统计队列中当前层剩余的结点数），并把该结点的值存入一个列表。如果取出的结点有左右子结点，则把左右子结点一次存入队列，并用nextCount统计下一层的结点数，为下一层访问做准备。当前层的结点全部取出后，把当前层的列表存入一个大的列表。

我的程序（Java）

import java.util.*; /** * 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 LinkedList<>(); List<List<Integer>> list = new LinkedList<>(); // 初始化大的列表 Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 初始化队列，用于存储树的结点 queue.offer(root); int thisCount = 1; // 记录当前层的结点数 int nextCount = 1; // 记录下一层的结点数 while(!queue.isEmpty()){ List<Integer> shortList = new LinkedList<Integer>(); thisCount = nextCount; // 获得当前层结点数 nextCount = 0; // 下一层结点数置零 while(thisCount != 0){ // 把队列中当前层的元素取光为止 TreeNode node = queue.poll(); // 取出队首的结点 shortList.add(node.val); // 把该结点中的值添加到小列表中 thisCount--; // 当前层访问完一个结点，数量减一 if(node.left != null){ // 当前访问结点有左子结点 queue.offer(node.left); // 则把该左子结点添加到队尾 nextCount++; // 下一层待访问结点数加1 } // 因为层序遍历在每一层都是从左到右的，队列是先进先出，所以先存左子结点，然后再右子结点 if(node.right != null){ // 当前访问结点有右子结点 queue.offer(node.right); // 则把该右子结点添加到队尾 nextCount++; // 下一层待访问结点数加1 } } list.add(shortList); // 把当前层的元素列表添加到大列表中 } return list; } }

补充知识点（嵌套的List实现方式）

List是一个接口，它的实现类有ArrayList和LinkedList。 嵌套List的初始化形式有如下几种（以List<List<Integer>>为例）：

List<List<Integer>> list = new LinkedList<>();List<List<Integer>> list = new LinkedList();List<List<Integer>> list = new LinkedList<List<Integer>>();

以上三种方法我都测试过，可以通过编译，一般采用第一种方法初始化。其他情况只要把Integer或者LinkedList替换掉即可。

如有不当之处，欢迎读者批评指正！