- 什么时候要限制层与层 注意计数的是节点个数还是层数
- 什么时候set visited on graph or board, many times on tree we don't need it
- Uses a queue
- Checks whether a vertex has been discovered before enqueueing the vertex rather than delaying this check until the vertex is dequeued from the queue.
- 什么时候用BFS Over DFS -- 最短距离
199. Binary Tree Right Side View
变形BFS return every level's last value. Identify each level but in the level order traversal first push the right node then push the left node because Queue is first in first out structure.. O(N)
public List<Integer> rightSideView(TreeNode root) {
List<Integer>result=new ArrayList<Integer>();
if(root == null){
return result;
}
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
result.add(root.val);
while(!q.isEmpty()){
int size = q.size();
while(size!= 0){
TreeNode pop = q.poll();
if(pop.right!= null){
q.add(pop.right);
}
if(pop.left!= null){
q.add(pop.left);
}
size--;
}
if(!q.isEmpty())result.add(q.peek().val);
}
return result;
}
111. Minimum Depth of Binary Tree
Use BFS, return when encounter the first leafnode 也可以用DFS Recurtion
public class Solution {
public int minDepth(TreeNode root) {
if(root == null)return 0;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
int num = 1;
while(!q.isEmpty()){
int size = q.size();
for(int i = 0;i < size;i++){
TreeNode cur = q.poll();
//first encounter leave node
if(cur.left == null && cur.right == null)return num;
if(cur.left!=null)q.offer(cur.left);
if(cur.right!=null)q.offer(cur.right);
}
num++;
}
return num;
}
}
261. Graph Valid Tree
Tree: The given edges number is equal to the #node - 1. No cycle, when BFS track the number of nodes visited.
BFS: when do we mark the node as being visited? Could also be solved using DFS
public class Solution {
public boolean validTree(int n, int[][] edges) {
if(n == 0||edges == null||edges.length != n-1)return false;
// initialize adjacency list
List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);
// initialize vertices
for (int i = 0; i < n; i++)
adjList.add(i, new ArrayList<Integer>());
// add edges
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0], v = edges[i][1];
adjList.get(u).add(v);
adjList.get(v).add(u);
}
boolean[] visited = new boolean[n];
Queue<Integer> q = new LinkedList<Integer>();
q.offer(0);
visited[0] = true;
int visit = 0;
while(!q.isEmpty()){
int cur = q.poll();
visit++;
for(int k:adjList.get(cur)){
if(visited[k])continue;
q.offer(k);
visited[k] = true;
}
}
return visit == n;
}
}
200. Number of Islands
BFS without modifying the original char array
class Point{
public int x;
public int y;
public Point(int x,int y){
this.x = x;
this.y = y;
}
}
public class Solution {
public int numIslands(char[][] grid) {
if(grid == null||grid.length == 0||grid[0].length == 0){
return 0;
}
int m = grid.length;
int n = grid[0].length;
int islands = 0;
boolean[][] visited = new boolean[m][n];
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
if(grid[i][j]=='1'&&!visited[i][j]){
bfs(grid,i,j,visited);
islands++;
}
}
}
return islands;
}
public void bfs(char[][] grid,int i,int j,boolean[][] visited){
int[] dx = {0,-1,1,0};
int[] dy = {-1,0,0,1};
Queue<Point> q = new LinkedList<Point>();
q.offer(new Point(i,j));
visited[i][j] = true;
while(!q.isEmpty()){
Point cur = q.poll();
//check four directions
for(int k = 0;k < 4;k++){
int x = cur.x + dx[k];
int y = cur.y + dy[k];
if(!inBound(grid,x,y))continue;
if(!visited[x][y]&&grid[x][y]=='1'){
q.offer(new Point(x,y));
visited[x][y] = true;
}
}
}
}
public boolean inBound(char[][] grid,int x,int y){
int m = grid.length;
int n = grid[0].length;
if(x >= 0 && x < m && y >=0 && y < n)return true;
return false;
}
}
301. Remove Invalid Parentheses
BFS的解法确保每次去除一个 一层一层 只移除“（”或者“）”
一旦出现合法的 停止去除操作 将队列里剩余的String加到总结果里 这里用一个found代表是否找到了 然后有一个判断
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<String>();
if(s == null) return result;
Queue<String> q = new LinkedList<String>();
HashSet<String> visited = new HashSet();
q.add(s);
visited.add(s);
boolean found = false;
//只要找到了就不再继续delete,因为我们要找寻的是minimum
while(!q.isEmpty()){
String cur = q.poll();
if(isValid(cur)){
result.add(cur);
found = true;
}
if(found)continue;
//continue deleting the character generate the possibility of deleting a "(" or ")"
for(int i = 0;i < cur.length();i++){
if(cur.charAt(i)!='('&&cur.charAt(i)!=')') continue;
//delete a posific position of character
String tmp = cur.substring(0,i) + cur.substring(i+1);
if(!visited.contains(tmp)){
visited.add(tmp);
q.offer(tmp);
}
}
}
return result;
}
boolean isValid(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') count++;
if (c == ')'){
if(count==0) return false;
count--;
}
}
return count == 0;
}
}
513. Find Bottom Left Tree Value
第一个想法是通过树的高度入手 太慢了！The first node in the last level of node
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
* My first thought was to count the height and stop the level order traverse
* until hit the height - 1 level. Slow! Only need a variable to record the start of each level
*/
public class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> q = new LinkedList();
q.add(root);
int height = getHeight(root);
int count = 0;
while(!q.isEmpty()&&count < height - 1){
int size = q.size();
for(int i = 0;i < size;i++){
TreeNode cur = q.poll();
if(cur.left != null)q.offer(cur.left);
if(cur.right != null)q.offer(cur.right);
}
count++;
}
return q.peek().val;
}
public int getHeight(TreeNode root){
if(root == null)return 0;
return 1 + Math.max(getHeight(root.left),getHeight(root.right));
}
}
public class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> q = new LinkedList();
q.add(root);
int result = 0;
while(!q.isEmpty()){
int size = q.size();
for(int i = 0;i < size;i++){
TreeNode cur = q.poll();
if(i == 0) result = cur.val;
if(cur.left != null)q.offer(cur.left);
if(cur.right != null)q.offer(cur.right);
}
}
return result;
}
}
101. Symmetric Tree
嗯这道题也是可以用BFS解决的 我们用层序遍历 对撞比较
286. Walls and Gates
BFS Way / DFS WAY branching from the empty place