一、前言

算法每日练习已经玩到了二叉树的层序遍历，也是很有趣的，今天就和大家一起学习一下什么是二叉树的层序排列和我的习惯解法，同时利用 LeetCode上十道题来巩固我们的学习结果

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

二、从 LeetCode 102.二叉树的层序遍历开始讲起

题目描述

解题思路

• 由题可知，要求输出是按照二叉树每层的元素来做输出
  
• 我使用队列来对二叉树每层元素进行存储和输出
  
• 根据队列的长度可以判断出当前层的元素个数并遍历
  
• 首先去判断入参是否为 null

• 如果为 null则直接返回 null

• 创建队列对象
  
• 将 root放入队列
  
• 遍历队列是否为 null

• 因为我们会把每层元素都放入到队列中， 如果队列为 null则代表二叉树已经遍历完了

• 创建一个 list集合保存元素 val
  
• 获取当前队列长度

• 当前队列长度就代表着当前二叉树层级的节点个数

• 遍历获取二叉树当前层级的节点

• 这里别忘记 size--；

• 判断当前节点的左右两个节点是否为 null， 不为 null则加入队列
  

代码展示

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 返回值
        List<List<Integer>> result = new ArrayList<>();
        // 如果如此那为 null，则直接返回
        if(root == null){
            return result;
        }
        // 设置队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer( root);
        // 循环遍历
        while(!queue.isEmpty()){
            // 创建当前层级的 list
            List<Integer> list = new ArrayList<>();
            // 获取当前层级的节点个数
            int size = queue.size();
            while(size > 0){
                // 获取当前节点
                TreeNode poll = queue.poll();
                if (poll.left != null){
                    queue.offer(poll.left);
                }
                // 将右节点放入队列中
                if (poll.right != null){
                    queue.offer(poll.right);
                }
                list.add(poll.val);
                size--;
            }
            // 将左节点放入队列中
            result.add(list);
        }
        return result;
    }
}
复制代码

结果分析

三、107.二叉树的层次遍历II

题目描述

解题思路

• 和上一题的唯一区别就是上一题是自顶上下遍历， 这道题是自下向上遍历
• 那么直接在上一题的基础上增加一个栈来存储每层节点元素
• 最后返回之前做一个弹栈操作就可以了， 具体可看下面代码展示

代码展示

提交结果

四、199.二叉树的右视图

题目描述

解题思路

• 这道题需要注意如下

• 题中有说，是右视图，而不是获取最右节点

• 实际的解题方法还是在 102的基础上遍历每一层节点获取 list
• 在遍历 list获取每一层节点的最后一个节点
• 然后返回就可以了， 具体代码请看代码展示

代码展示

提交结果

五、637.二叉树的层平均值

题目描述

解题思路

• 一样的， 遍历每层节点的时候记录数值然后除一下就可以了
• 这里需要注意的是要用double接收

代码展示

提交结果

六、429.N叉树的层序遍历

题目描述

解题思路

• 这边需要注意的是二叉树变成了 n叉树， 其余不变
• 就是在我们添加每层节点的时候判断左右节点为 null变成了遍历添加就 ok