广州网站改版设计,公司网站建设济宁,国内新闻,漯河网站建设服务公司BFS#xff08;宽搜#xff09; 宽度优先遍历和深度优先遍历组成了大家熟悉的搜索算法#xff0c;这两种算法也是蓝桥杯之类竞赛题的常考思想#xff0c;正巧马上蓝桥杯临近#xff0c;博主也是刷了很多BFS相关的题型#xff0c;在这篇文章中会从力扣上选取三道简单的宽搜…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 ListNode children;public Node() {}public Node(int _val) {val _val;}public Node(int _val, ListNode _children) {val _val;children _children;}
};
*/class Solution {public ListListInteger levelOrder(Node root) {ListListInteger listsnew ArrayList();if(rootnull){return lists;}QueueNode qnew LinkedListNode();q.add(root);while(!q.isEmpty()){int szq.size();ListInteger listnew ArrayList();for(int i0;isz;i){Node curq.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(rootnull){return 0;}int max1;QueuePairTreeNode,Integer qnew LinkedList();q.add(new Pair(root,1));while(!q.isEmpty()){int szq.size();int head0,last0;for(int i0;isz;i){PairTreeNode,Integer pq.poll();TreeNode curp.getKey();int vp.getValue();if(cur.left!null){q.add(new Pair(cur.left,v*2));}if(cur.right!null){q.add(new Pair(cur.right,v*21));}if(i0){headv;}if(i(sz-1)){lastv;}}maxmax(last-head1)?max:(last-head1);}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 ListInteger largestValues(TreeNode root) {ListInteger listnew ArrayList();if(rootnull){return list;}QueueTreeNode qnew LinkedList();q.add(root);while(!q.isEmpty()){int szq.size();int maxInteger.MIN_VALUE;for(int i0;isz;i){TreeNode curq.poll();if(cur.left!null){q.add(cur.left);}if(cur.right!null){q.add(cur.right);}maxmaxcur.val?max:cur.val;}list.add(max);}return list;}
} ❤️ 我是小皮侠谢谢大家都能看到这里 主页已更新Java基础内容数据结构基础数据库算法 未来会更新Java项目SpringBootRedis以及各种Java路线会用到的技术。 求点赞求收藏求评论求关注 ♀️谢谢大家 我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code2upjellgk3eow
