【算法篇】三道题理解算法思想——认识BFS
【算法篇】三道题理解算法思想——认识BFS
BFS（宽搜）
宽度优先遍历和深度优先遍历组成了大家熟悉的搜索算法，这两种算法也是蓝桥杯之类竞赛题的常考思想，正巧马上蓝桥杯临近，博主也是刷了很多BFS相关的题型，在这篇文章中会从力扣上选取三道简单的宽搜题型，带大家了解BFS的模板以及对他有个初步认识。 本篇文章题目较为简单，大家可以根据第一题的模板，自己先去力扣上做题然后回来看题解，稍后我们继续更新难度更高的宽搜题目，希望大家能给个关注👍。
文章顺序：
题目链接-》算法思路-》代码呈现。
算法摘要：
宽度优先遍历是一种利用队列这种数据结构，从某一点开始，一层一层进行遍历的一种算法思想，而BFS（宽搜）实际上就是一种暴力搜索算法，利用宽度优先遍历来查找想要结果。
1.N叉树的层序遍历
题目链接：
https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
算法思路：
仅需多加⼀个变量，⽤来记录每⼀层结点的个数，然后层序遍历即可。
代码展示：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> lists=new ArrayList<>();
if(root==null){
return lists;
}
Queue<Node> q=new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
int sz=q.size();
List<Integer> list=new ArrayList<>();
for(int i=0;i<sz;i++){
Node cur=q.poll();
list.add(cur.val);
for(Node c:cur.children){
if(c!=null){
q.add(c);
}
}
}
lists.add(list);
}
return lists;
}
}2.二叉树的最大宽度
题目链接：
https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
算法思路：
依旧是利⽤层序遍历，但是这⼀次队列⾥⾯不单单存结点信息，并且还存储当前结点如果在数组中存 储所对应的下标（在我们学习数据结构 - 堆的时候，计算左右孩⼦的⽅式）。
这样我们计算每⼀层宽度的时候，⽆需考虑空节点，只需将当层结点的左右结点的下标相减再加 1 即可。
但是，这⾥有个细节问题：如果⼆叉树的层数⾮常恐怖的话，我们任何⼀种数据类型都不能存下下标的值。但是没有问题，因为
• 我们数据的存储是⼀个环形的结构；
• 并且题⽬说明，数据的范围在 int 这个类型的最⼤值的范围之内，因此不会超出⼀圈；
• 因此，如果是求差值的话，我们⽆需考虑溢出的情况。
代码展示：
/**
* 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 int widthOfBinaryTree(TreeNode root) {
if(root==null){
return 0;
}
int max=1;
Queue<Pair<TreeNode,Integer>> q=new LinkedList<>();
q.add(new Pair(root,1));
while(!q.isEmpty()){
int sz=q.size();
int head=0,last=0;
for(int i=0;i<sz;i++){
Pair<TreeNode,Integer> p=q.poll();
TreeNode cur=p.getKey();
int v=p.getValue();
if(cur.left!=null){
q.add(new Pair(cur.left,v*2));
}
if(cur.right!=null){
q.add(new Pair(cur.right,v*2+1));
}
if(i==0){
head=v;
}
if(i==(sz-1)){
last=v;
}
}
max=max>(last-head+1)?max:(last-head+1);
}
return max;
}
}3.在每个树行中找最大值
题目链接：
515. 在每个树行中找最大值 - 力扣（LeetCode）
算法思路：
层序遍历过程中，在执⾏让下⼀层节点⼊队的时候，我们是可以在循环中统计出当前层结点的最⼤值的。
因此，可以在 bfs 的过程中，统计出每⼀层结点的最⼤值。
代码展示：
/**
* 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<Integer> largestValues(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null){
return list;
}
Queue<TreeNode> q=new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
int sz=q.size();
int max=Integer.MIN_VALUE;
for(int i=0;i<sz;i++){
TreeNode cur=q.poll();
if(cur.left!=null){
q.add(cur.left);
}
if(cur.right!=null){
q.add(cur.right);
}
max=max>cur.val?max:cur.val;
}
list.add(max);
}
return list;
}
}