您现在的位置是：首页 >技术交流 >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>>();
        //判断树是否为null
        if (root == null) {
            return ret;
        }

        //创建一个队列，根据队列先进先出的特性，用于元素的入队出队
        ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();
        //先将根节点放入队列
        queue.add(root);
        //如果队列不为null
        while(!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;
        }
}