【算法题型总结】--6、BFS
2021/9/14 17:06:12
本文主要是介绍【算法题型总结】--6、BFS,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
// 计算从起点 start 到终点 target 的最近距离 int BFS(Node start, Node target) { Queue<Node> q; // 核心数据结构 Set<Node> visited; // 避免走回头路 q.offer(start); // 将起点加入队列 visited.add(start); int step = 0; // 记录扩散的步数 while (q not empty) { int sz = q.size(); /* 将当前队列中的所有节点向四周扩散 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); /* 划重点:这里判断是否到达终点 */ if (cur is target) return step; /* 将 cur 的相邻节点加入队列 */ for (Node x : cur.adj()) if (x not in visited) { q.offer(x); visited.add(x); } } /* 划重点:更新步数在这里 */ step++; } }
1、反转二叉树
方法1:BFS
//BFS class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) {return null;} ArrayDeque<TreeNode> deque = new ArrayDeque<>(); deque.offer(root); while (!deque.isEmpty()) { int size = deque.size(); while (size-- > 0) { TreeNode node = deque.poll(); swap(node); if (node.left != null) {deque.offer(node.left);} if (node.right != null) {deque.offer(node.right);} } } return root; } public void swap(TreeNode root) { TreeNode temp = root.left; root.left = root.right; root.right = temp; } }
其他方法
//DFS递归 class Solution { /** * 前后序遍历都可以 * 中序不行,因为先左孩子交换孩子,再根交换孩子(做完后,右孩子已经变成了原来的左孩子),再右孩子交换孩子(此时其实是对原来的左孩子做交换) */ public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } invertTree(root.left); invertTree(root.right); swapChildren(root); return root; } private void swapChildren(TreeNode root) { TreeNode tmp = root.left; root.left = root.right; root.right = tmp; } }
这篇关于【算法题型总结】--6、BFS的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南