本文主要是介绍BFS题型总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Word Ladder
思路：用level来判断step，注意三点：
1. getAllNeighbors 是chars[i] = nc, 然后chars[i] = ic还原；
2. 层级关系，一定要首先收集queue.size(),然后递减；
3. queue和hashset是一对好朋友，一定要一起出现，同时加入内容；
class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {if(beginWord == null || endWord == null || wordList == null || wordList.size() == 0) {return 0;}HashSet<String> dict = new HashSet<String>(wordList);HashSet<String> visited = new HashSet<String>();Queue<String> queue = new LinkedList<String>();queue.offer(beginWord);visited.add(beginWord);int step = 1;while(!queue.isEmpty()) {int size = queue.size();while(size > 0) {String node = queue.poll();size--;List<String> list = getAllNeighbors(node, dict);for(String nextnode : list) {if(nextnode.equals(endWord)) {return step + 1;}if(!visited.contains(nextnode)) {visited.add(nextnode);queue.offer(nextnode);}}}step++;}return 0;}private List<String> getAllNeighbors(String node, HashSet<String> dict) {List<String> result = new ArrayList<String>();char[] chars = node.toCharArray();for(int i = 0; i < chars.length; i++) {char ic = chars[i];for(char nc = 'a'; nc <= 'z'; nc++) {if(nc == ic) {continue;} chars[i] = nc;String newstr = new String(chars);if(dict.contains(newstr)){result.add(newstr);}}chars[i] = ic;}return result;}
}Number of Islands:
思路：这种一片一片的连通性问题，BFS是强项；注意三点：
1. 涉及到x,y坐标的时候，往往要开Queue<Integer> queueX queueY, 或者开一个Queue<Node>
2. int[] dx, int [] dy, 是标准模板写上下左右移动；
3. Visited一定要出现，因为坐标移动会出现死循环；
class Solution {public int numIslands(char[][] grid) {if(grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int n = grid.length;int m = grid[0].length;int count = 0;boolean[][] visited = new boolean[n][m];for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(grid[i][j] == '1' && !visited[i][j]) {bfs(grid, i, j, visited);count++;}}}return count;}private void bfs(char[][] grid, int x, int y, boolean[][] visited) {int[][] dirs = {{0,1}, {0,-1}, {-1,0}, {1,0}};int n = grid.length;int m = grid[0].length;Queue<int[]> queue = new LinkedList<int[]>();queue.offer(new int[]{x, y});visited[x][y] = true;while(!queue.isEmpty()) {int[] node = queue.poll();for(int k = 0; k < 4; k++) {int nx = node[0] + dirs[k][0];int ny = node[1] + dirs[k][1];if(0 <= nx && nx < n && 0 <= ny && ny < m && grid[nx][ny] == '1' && !visited[nx][ny]) {queue.offer(new int[]{nx, ny});visited[nx][ny] = true;}}}}
}Binary Tree Vertical Order Traversal
思路：就是左走index -1， 右走index+1，然后把相对应的index的key收集起来，那么就要用到hashmap，同时多用个iqueue，就是index queue，这样node和index同步，这样就收集到hashmap之后，同时更新最大最小的index，然后从小到大收集起来；
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public List<List<Integer>> verticalOrder(TreeNode root) {List<List<Integer>> lists = new ArrayList<List<Integer>>();if(root == null) {return lists;}HashMap<Integer, List<Integer>> hashmap = new HashMap<Integer, List<Integer>>();Queue<Integer> iqueue = new LinkedList<Integer>();Queue<TreeNode> nqueue = new LinkedList<TreeNode>();int maxindex = Integer.MIN_VALUE;int minindex = Integer.MAX_VALUE;nqueue.offer(root);iqueue.offer(0);while(!nqueue.isEmpty()) {TreeNode node = nqueue.poll();int index = iqueue.poll();maxindex = Math.max(maxindex, index);minindex = Math.min(minindex, index);if(hashmap.containsKey(index)) {hashmap.get(index).add(node.val);} else {List<Integer> list = new ArrayList<Integer>();list.add(node.val);hashmap.put(index, list);}if(node.left != null) {nqueue.offer(node.left);iqueue.offer(index - 1);}if(node.right != null) {nqueue.offer(node.right);iqueue.offer(index + 1);}}for(int i = minindex; i <= maxindex; i++) {lists.add(hashmap.get(i));}return lists;}
}Deep Copy Graph;
/*
// Definition for a Node.
class Node {public int val;public List<Node> neighbors;public Node() {val = 0;neighbors = new ArrayList<Node>();}public Node(int _val) {val = _val;neighbors = new ArrayList<Node>();}public Node(int _val, ArrayList<Node> _neighbors) {val = _val;neighbors = _neighbors;}
}
*/
class Solution {public Node cloneGraph(Node node) {if(node == null) {return null;}HashMap<Node, Node> hashmap = new HashMap<Node, Node>();HashSet<Node> set = new HashSet<Node>();Queue<Node> queue = new LinkedList<Node>();queue.offer(node);set.add(node);// copy each node;while(!queue.isEmpty()) {Node head = queue.poll();if(!hashmap.containsKey(head)) {hashmap.put(head, new Node(head.val));}for(Node neighbor : head.neighbors) {if(!set.contains(neighbor)) {set.add(neighbor);queue.offer(neighbor);}}}// copy edges;for(Node n: set) {for(Node neighbor: n.neighbors) {hashmap.get(n).neighbors.add(hashmap.get(neighbor));}}return hashmap.get(node);}
}Deep copy 其实也可以用DFS写，简单点，不过DFS面试的时候一定要说有可能会爆栈，如果图很大的话；
class Solution {public Node cloneGraph(Node node) {if(node == null) {return null;}HashMap<Node, Node> hashmap = new HashMap<Node, Node>();return clone(node, hashmap);}private Node clone(Node node, HashMap<Node, Node> hashmap) {if(hashmap.containsKey(node)) {return hashmap.get(node);} else {Node newnode = new Node(node.val);hashmap.put(node, newnode);for(Node neighbor : node.neighbors) {hashmap.get(node).neighbors.add(clone(neighbor, hashmap));}return newnode;}}
}All Nodes distance k in binary tree.
思路：把tree build up成图，left, right, parent 全部是neighbor，然后在图里面做BFS，记录当前层的node，注意如果 K == 0 就是收集这个点；
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {List<Integer> list = new ArrayList<Integer>();HashMap<Integer, HashSet<Integer>> hashmap = new HashMap<Integer, HashSet<Integer>>();buildGraph(hashmap, root, null);HashSet<Integer> set = new HashSet<Integer>();Queue<Integer> queue = new LinkedList<Integer>();queue.offer(target.val);set.add(target.val);int step = K;while(!queue.isEmpty()) {int size = queue.size();while(size > 0) {Integer integer = queue.poll();size--;// collect current level;if(step == 0) {list.add(integer);}// collect next level;for(Integer neighbor: hashmap.get(integer)) {if(!set.contains(neighbor)) {set.add(neighbor);queue.offer(neighbor);}}}step--;}return list;}private void buildGraph(HashMap<Integer, HashSet<Integer>> hashmap, TreeNode root, TreeNode parent) {if(root == null) {return;}// add node;hashmap.putIfAbsent(root.val, new HashSet<Integer>());// add neighbors;if(root.left != null) {hashmap.get(root.val).add(root.left.val);}if(root.right != null) {hashmap.get(root.val).add(root.right.val);}if(parent != null) {hashmap.get(root.val).add(parent.val);}buildGraph(hashmap, root.left, root);buildGraph(hashmap, root.right, root);}
}Closest Leaf in a Binary Tree
思路：跟上面那题一样，把Tree build成graph，然后在graph上面做BFS
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public int findClosestLeaf(TreeNode root, int k) {if(root == null) {return -1;}HashMap<TreeNode, HashSet<TreeNode>> hashmap = new HashMap<TreeNode, HashSet<TreeNode>>();buildGraph(root, hashmap, null);TreeNode knode = findNode(hashmap, k); Queue<TreeNode> queue = new LinkedList<TreeNode>();HashSet<Integer> visited = new HashSet<Integer>();queue.offer(knode);visited.add(k);while(!queue.isEmpty()) {TreeNode node = queue.poll();if(node.left == null && node.right == null) {return node.val;}for(TreeNode neighbor: hashmap.get(node)) {if(!visited.contains(neighbor.val)) {visited.add(neighbor.val);queue.offer(neighbor);}}}return -1;}private TreeNode findNode(HashMap<TreeNode, HashSet<TreeNode>> hashmap , int target) {for(TreeNode node: hashmap.keySet()) {if(node.val == target) {return node;}}return null;}private void buildGraph(TreeNode root, HashMap<TreeNode, HashSet<TreeNode>> hashmap, TreeNode parent) {if(root == null) {return;}hashmap.putIfAbsent(root, new HashSet<TreeNode>());if(root.left != null) {hashmap.get(root).add(root.left);}if(root.right != null) {hashmap.get(root).add(root.right);}if(parent != null) {hashmap.get(root).add(parent);}buildGraph(root.left, hashmap, root);buildGraph(root.right, hashmap, root);}
}Serialize and Deserialize BST
思路：用preorder来构建string，因为preorder知道第一个就是root，找到后面大于root的点，就是right tree，注意null，用stringbuilder构建string。Time : O(N) serialize, O(N^2) deserialize;因为要循去找比root大的，T(n) = O(n) + T(n-1) ==> T(n) = O(n^2); 这题跟serialize BT不一样的地方是：一定要利用BST的性质，也就是root, left, right.这个性质BT没有；
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
public class Codec {private final String NULL = "null";private final String DELIMITER = ",";// Encodes a tree to a single string.public String serialize(TreeNode root) {StringBuilder sb = new StringBuilder();serializeHelper(root, sb);return sb.toString().substring(0, sb.length() -1);}private void serializeHelper(TreeNode root, StringBuilder sb) {if(root == null) {sb.append(NULL).append(DELIMITER);return;} else {sb.append(root.val).append(DELIMITER);serializeHelper(root.left, sb);serializeHelper(root.right, sb);}}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] splits = data.split(DELIMITER);return buildTree(splits, 0, splits.length - 1);}private TreeNode buildTree(String[] splits, int start, int end) {if(start > end || splits[start].equals(NULL)) {return null;}TreeNode node = new TreeNode(Integer.parseInt(splits[start]));int i = start + 1;for(; i <= end; i++) {if(splits[i].equals(NULL)) {continue;}if(Integer.parseInt(splits[i]) > node.val) {break;}}node.left = buildTree(splits, start + 1, i -1);node.right = buildTree(splits, i, end);return node;}
}// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));Serialize and Deserialize Binary Tree
思路：level order travel，然后 level order 去build；核心思想就是左右左右的build，用queue level order收集，那么我们也要用queue来level order还原，deserilize的时候，用queue来收集下一层的node从而来build整个tree；
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
public class Codec {private String EMPTY_NODE = "#";private String DILIMITER = ",";// Encodes a tree to a single string.public String serialize(TreeNode root) {StringBuilder sb = new StringBuilder();dfs(root, sb);return sb.toString();}private void dfs(TreeNode root, StringBuilder sb) {if(root == null) {sb.append(EMPTY_NODE).append(DILIMITER);return;}sb.append(root.val).append(DILIMITER);dfs(root.left, sb);dfs(root.right, sb);}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if(data.isEmpty()) {return null;}String[] splits = data.split(DILIMITER);Queue<String> queue = new LinkedList<String>();for(String split: splits) {queue.offer(split);}return build(queue);}private TreeNode build(Queue<String> queue) {if(queue.isEmpty()) {return null;}String nodeval = queue.poll();if(nodeval.equals(EMPTY_NODE)) {return null;}TreeNode node = new TreeNode(Integer.parseInt(nodeval));node.left = build(queue);node.right = build(queue);return node;}
}// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));The Maze
思路：注意题目是球选择一个方向，然后一直走到头，中间的0，不代表能够到达，只有最后一个node才算到达；
注意，走的过程就是一个while循环，一直走，技巧就是while(isvalid(maz, nx + dx[k], ny + dy[k]) 这里注意一点就是走的过程中并不需要判断是否visited过，走到碰墙了，才判断是否visited过。
class Solution {private class Node {public int x;public int y;public Node(int x, int y) {this.x = x;this.y = y;}}public boolean hasPath(int[][] maze, int[] start, int[] destination) {if(maze == null || maze.length == 0 || maze[0].length == 0) {return false;}int n = maze.length;int m = maze[0].length;Queue<Node> queue = new LinkedList<Node>();boolean[][] visited = new boolean[n][m];queue.offer(new Node(start[0], start[1]));visited[start[0]][start[1]] = true;int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};while(!queue.isEmpty()) {Node node = queue.poll();if(node.x == destination[0] && node.y == destination[1]) {return true;}for(int[] dir: dirs) {int nx = node.x;int ny = node.y;// 这里triky的地方就是参数要加上dx, dy，这样判断下一个是否合法；// 如果不合法，跳出循环，那么下面的visited就不会是invalid情况了；while(isvalid(nx + dir[0], ny + dir[1], maze)) {nx += dir[0];ny += dir[1];}if(!visited[nx][ny]) {queue.offer(new Node(nx, ny));visited[nx][ny] = true;} }}return false;}private boolean isvalid(int x, int y, int[][] maze) {int n = maze.length;int m = maze[0].length;return (0 <= x && x < n && 0 <= y && y < m && maze[x][y] != 1);}
}这篇关于BFS题型总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
