leetcode【二叉树—中等】102.二叉树的层次遍历

文章目录

• 前言
• 题目
• 题解
• NO1：BFS（借助队列）
• NO2：DFS（深搜，借助递归实现）
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为二叉树专题。

---

题目

题目来源leetcode

leetcode地址：102. 二叉树的层序遍历，难度：简单。

题目描述(摘自leetcode)：

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

示例：
二叉树：[3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果：
[
  [3],
  [9,20],
  [15,7]
]

---

题解

NO1：BFS（借助队列）

思路：借助队列来实现层次遍历，要想记录每一层的元素值，那么就需要在每一层进行遍历前先获取队列中的元素数量，通过该数量来进行依次出队进而能够确定每层的元素值。

代码：

//层次遍历
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> itemList = new ArrayList<>();
    if(root == null){
        return itemList;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size = queue.size();//记录当前层的节点数量，用于之后每次节点的数量统计
        List<Integer> item = new ArrayList<>();
        while(size > 0){
            //出队，获取该节点的值
            TreeNode node = queue.poll();
            item.add(node.val);
            //入队左右节点
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
            size--;
        }
        itemList.add(item);
    }
    return itemList;
}

---

NO2：DFS（深搜，借助递归实现）

思路：想要使用递归来进行层次遍历，这里设置的出口为遍历的叶子节点为null。对于在第n层位置以及该n层存储的值则通过一个deep变量(深度的意思)来表示，每一层可能都会有多个节点，所以说我们需要来通过集合中数量与深度比较确保每层只创建一个集合。

代码：

private List<List<Integer>> itemList = new ArrayList<>();

//层次遍历：DFS
public List<List<Integer>> levelOrder(TreeNode root) {
    dfsLevelOrder(root, 0);
    return itemList;
}

/**
  * DFS来进行层次遍历
  *
  * @param root 节点
  * @param deep 深度
  */
public void dfsLevelOrder(TreeNode root, int deep) {
    if (root == null) {  //出口
        return;
    }
    deep++; //深度+1
    //某deep深度的节点判断是否要创建集合
    if (itemList.size() < deep) {
        itemList.add(new ArrayList<>());
    }
    itemList.get(deep - 1).add(root.val);

    //依次进行左右节点递归遍历
    dfsLevelOrder(root.left, deep);
    dfsLevelOrder(root.right, deep);
}

---

参考文章

[1]. leetcode题解

[2]. 代码随想录—102.二叉树的层序遍历

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.10.12