序言
虽然算法很难，但不应该就放弃。这是一个学习笔记，希望你们喜欢~
先自己尝试写，大概十几分钟仍然写不出来
看思路，再尝试跟着思路写
仍然写不出来，再看视频
b站up视频推荐：爱学习的饲养员
leetcode其他文章：
数组篇：
链表篇：
从小白开始刷算法 ListNode 链表篇 leetcode.203
从小白开始刷算法 ListNode 链表篇 leetcode.206
队列篇
从小白开始刷算法 ListNode 链表篇 leetcode.933
栈篇
从小白开始刷算法 Stack 栈篇 leetcode.496
哈希篇
从小白开始刷算法 Hash 哈希篇 leetcode.217
从小白开始刷算法 Hash 哈希篇 leetcode.705
树篇
从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144
从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94
从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94
堆篇
从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215
小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692
双指针篇
二分法篇
滑动窗口篇
递归篇
分治法篇
回溯法篇
dfs篇
bfs篇
难度：中等
题目：
102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
题目来源：力扣（LeetCode）
bfs介绍：
BFS（广度优先搜索）是一种图遍历算法，用于在一个图或树的数据结构中从给定的起始节点开始，逐层地向外探索并访问其邻居节点。
BFS 的基本思想是通过维护一个队列来实现。起始时将起始节点放入队列中，然后从队列中取出一个节点，访问该节点，并将其未访问过的邻居节点放入队列中。然后继续从队列中取出节点，重复上述操作，直到队列为空。
BFS 的过程可以用以下步骤概括：
- 创建一个空队列，并将起始节点放入队列中。
- 标记起始节点为已访问。
- 当队列非空时，执行以下操作：
- 从队列中取出一个节点。
- 访问该节点。
- 将该节点的未访问过的邻居节点放入队列中，并标记为已访问。
- 重复步骤 3，直到队列为空。
BFS 通常用于解决以下问题：
- 搜索最短路径：BFS 在图中搜索最短路径的能力使其非常适用于寻找两个节点之间的最短路径。
- 遍历或搜索树或图：BFS 可以用于遍历或搜索树或图的所有节点，确保每个节点都被访问到。
- 连通性检测：BFS 可以用于检测图或树中的连通性，即确定是否存在从一个节点到另一个节点的路径。
bfs思路
能否写出：能写出。
时间：15分钟多 比dfs好理解
思路：
主要是进入循环，直到队列q为空：
- 获取当前队列中的节点数量
size，这个数量表示当前层的节点个数。 - 创建一个空的列表
list，用于存储当前层的节点值。 - 在 size 的范围内进行迭代：
- 从队列中取出一个节点
current。 - 将
current的值加入list列表。 - 如果
current的左子节点不为空，将其加入队列q。 - 如果
current的右子节点不为空，将其加入队列q。
- 将
list列表加入res列表，表示当前层的节点值已经遍历完毕。
- 返回最终的
res列表。
通过队列实现了层次遍历，利用队列的先入先出特性，保证了按层遍历节点，并且按层存储节点值。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> q = new LinkedList<>(); q.add(root); ArrayList<List<Integer>> res = new ArrayList<>(); if(root==null){ return res; } while (!q.isEmpty()){ //获取当前队列中的节点数量 size，这个数量表示当前层的节点个数 int size = q.size(); ArrayList<Integer> list = new ArrayList<>(); while (size>0){ TreeNode current = q.poll(); list.add(current.val); //如果 current 的左子节点不为空，将其加入队列 q if(current.left!=null){ q.add(current.left); } //如果 current 的右子节点不为空，将其加入队列 q if(current.right!=null){ q.add(current.right); } size--; } //把list复制进去 res.add(new ArrayList<>(list)); } return res; } }
时间复杂度：O(N) 其中
- N 表示节点的总数。
空间复杂度：O(N)
- 算法使用了队列来辅助遍历，队列的最大空间取决于每层节点的个数，最坏情况下为 O(N)。
其他思路
dfs：
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } dfs(root, result, 0); return result; } private void dfs(TreeNode node, List<List<Integer>> result, int level) { //如果当前层级大于result长度证明还没有创建 if (level > result.size()-1) { result.add(new ArrayList<>()); } result.get(level).add(node.val); //递归左节点 if (node.left != null) { dfs(node.left, result, level+1); } //递归右节点 if (node.right != null) { dfs(node.right, result, level+1); } } }
