行业知识
宽度优先搜索算法(BFS)
宽度优先搜索算法(BFS)是什么?
宽度优先���索算法(BFS)(也称为广度优先搜索)主要运用于树、图和矩阵(这三种可以都归类在图中),用于在图中从起始顶点开始逐层地向外探索,直到找到目标顶点为止。
在本篇文章中,我们主要讨论其在树中的运用
树的宽度优先搜索
树的宽度优先搜索 即 树的层序遍历 :逐层访问树的节点,并按照层级顺序输出节点的值。从树的根节点开始,逐层向下遍历,先访问当前层的所有节点,然后再访问下一层的节点,依次类推直到遍历完整棵树
其过程如下图所示:
如何实现树的层序遍历呢?
我们在遍历每一层节点时,都是从左向右依次遍历的,即先遍历上一层节点中的第一个节点的孩子节点 ,即优先遍历前面的节点,此时,满足 “先进先出”,因此,我们可以使用队列来帮助我们完成层序遍历
具体步骤如下:
1. 先将根节点放入队列中
2. 从队列中出队一个节点,并将该节点的所有孩子节点(如果有)依次放入队列中
3. 继续取出节点,指导队列为空
4. 当队列为空时,遍历完成
接下来,我们通过一些练习来进一步体会和掌握BFS
相关练习
练习1:N叉树的层序遍历
题目链接:
429. N 叉树的层序遍历 - 力扣(LeetCode)
题目描述:
给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。
树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6]输出:[[1],[3,2,4],[5,6]]
示例 2:
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示:
- 树的高度不会超过 1000
- 树的节点总数在 [0, 10^4] 之间
思路分析:
本题要求我们返回N叉树节点值的层序遍历,且以 List类型的结果返回,即每一层使用一个列表来存储本层的所有节点的值,然后将这些列表放到一个列表中返回
在这里,我们可以使用队列来帮助我们进行层序遍历,但在将节点出队时,也会将其孩子节点放入队列中,那么,我们如何区分每一层的节点呢?
我们可以使用一个变量 count 在节点出队之前,记录队列当前节点个数(即这一层节点个数),然后再将这 count 个节点依次出队列,将其节点值放入列表中,同时将其孩子节点放入队列中
具体步骤:
1. 先判断树是否为空,不为空将根节点放入队列中
2. 记录当前队列中包含的节点个数count
3. 将count个节点依次出队列,将其节点值放入一个临时列表中,同时将其孩子节点放入队列中
4. 遍历完count个节点后,临时列表中就存放了这一层所有节点的值,然后再将临时列表放入结果列表中
5. 继续遍历,直到队列为空
6. 返回结果
代码实现:
class Solution { public List levelOrder(Node root) { List ret = new ArrayList(); Node cur = root; Queue queue = new ArrayDeque(); //先将根节点放入队列中 if(cur == null) return ret; queue.add(cur); int count = 0; while (!queue.isEmpty()){ //先记录当前队列中节点个数 count = queue.size(); List tmp = new ArrayList();//使用临时表存储这一层节点的值 for (int i = 0; i练习2:二叉树的锯齿形层序遍历
题目链接:
103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode)
题目描述:
给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 1:
输入:root = [3,9,20,null,null,15,7]输出:[[3],[20,9],[15,7]]
示例 2:
输入:root = [1]输出:[[1]]
示例 3:
输入:root = []输出:[]
提示:
- 树中节点数目在范围 [0, 2000] 内
- -100
上一篇:原神账户怎么还服务器?
下一篇:要怎么ping远处服务器?