102. 二叉树的层序遍历

二叉树的层序遍历需要队列数据结构，还需要记录每一层节点的个数，可以定义一个变量记录，也可以直接使用队列中元素个数表示每一层的节点个数，每次获取队列头中的节点后，需要判断该节点是否有左右孩子，如果有，则放入队列，并且将记录每一层节点个数的变量加一。

// 二叉树的层序遍历-变量记录每层节点个数
public List<List<Integer>> levelOrder(TreeNode root) {// 存储结果List<List<Integer>> result = new ArrayList<>();// 如果根节点为空，则直接返回结果if (root == null) {return result;}// 创建一个队列Queue<TreeNode> queue = new LinkedList<>();// 将根节点放入队列queue.offer(root);// 记录每一层的节点个数int c1 = 1;//每一层节点个数// 当队列不为空时while (!queue.isEmpty()) {// 记录下一层节点个数int c2 = 0;//下一层节点个数// 创建一个存储每一层节点的列表List<Integer> lever = new ArrayList<>();// 遍历每一层节点for (int i = 0; i < c1; i++) {// 从队列中取出一个节点TreeNode node = queue.poll();// 将节点的值添加到列表中lever.add(node.val);// 如果该节点有左子节点，则将左子节点放入队列if (node.left != null) {queue.offer(node.left);c2++;}// 如果该节点有右子节点，则将右子节点放入队列if (node.right != null) {queue.offer(node.right);c2++;}}// 更新每一层节点个数c1 = c2;// 将每一层节点列表添加到结果中result.add(lever);}// 返回结果return result;
}

//二叉树的层序遍历-直接使用队列长度表示每层节点个数
public static List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return result;}queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<>();// 直接使用队列的长度表示每一层节点的个数int size = queue.size();for (int i = 0; i < size; i++) {TreeNode polled = queue.poll();level.add(polled.val);// 如果有左右孩子，则加入队列if(polled.left!=null){queue.offer(polled.left);}if(polled.right!=null){queue.offer(polled.right);}}result.add(level);}return result;}

之所以可以使用队列长度直接表示每层节点个数是因为，从根节点开始，节点个数为1，这是已知的，在遍历当前层时，将当前层的节点全部弹出，又把下一层的节点全部入队，因此，只要遍历到下一层（当前层有孩子），那么说明此时的队列中的长度就是当前层的节点个数（即没有上一层节点，又没有下一层节点）。