102. 二叉树的层序遍历【206】

难度等级：中等

上一篇算法：

 215. 数组中的第K个最大元素【382】

力扣此题地址：

102. 二叉树的层序遍历 - 力扣（Leetcode）

1.题目：102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

2.解题思路：

思路：

1.先判断这个树是否为空，为空则直接返回。

2.树不为空，我们将根节点放入一个队列中，然后每次取出这个节点后，相应的将他的左右子节点依次放入队列中，按照队列的先进先出的特性，依次将元素出队列。（难理解可以画图感受一下）

二叉树概念及基本功能实现

代码实现步骤：

1.先创建一个list，用于存放每层的元素，list中的元素以list为单位，每个单位存放一层元素

2.判断树是否为null

3.创建一个队列，用于元素的入队出队，根据队列先进先出的特性，保证元素的顺序性

4.将根节点加入队列

5.开始循环，判断队列是否为null，不为null则继续循环（一次循环代表遍历一层）

        （1）先创建个list链表，用于存放每层的元素

        （2）获取当前队列的长度，也就是每层有多少个元素

        （3）进入for循环，队列的长度就是终止条件，for循环中：需要将已有的元素出队并放入list链表中，将对应的左右子节点依次放入队列中。

        （4）执行完（1）（2）（3）后，将这一层的元素的list集合作为一个元素放入到最终的list链表中

6.return 链表

3.代码实现：

/* Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {//先创建一个List链表，作为返回值List<List<Integer>> ret = new ArrayList<List<Integer>>();//判断树是否为nullif (root == null) {return ret;}//创建一个队列，根据队列先进先出的特性，用于元素的入队出队ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();//先将根节点放入队列queue.add(root);//如果队列不为nullwhile(!queue.isEmpty() ){//因为list返回值类型中，每个元素是一个List链表，//所以在每遍历完一层后就创建一个list，将每层的元素分别放入list中作为元素返回List<Integer> level = new ArrayList<Integer>();//获取每层的结点个数，用于循环终止条件int currentLevelSize = queue.size();for (int i = 1; i <= currentLevelSize; ++i) {//出队TreeNode node = queue.poll();//将出队的元素放入list中level.add(node.val);//判断左右子树是否为null，不为null就对应地将元素从左到右添加到队列中if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}//每一层遍历完就放入ret中ret.add(level);}return ret;}
}