DFS BFS
Key points:
DFS-stack&recursion, BFS-queue
If BFS works, never use DFS because of StackOverflow, important! like this one: surrounded-regions
DFS:
A and B is connected?
Connected component. (Union Find is faster because no need to build graph)
Search path
Has cycle
two color
Backtracking, all results
BFS:
shortest path
connected component
topological sorting
level order traversal
Topological sorting
Need to mark visited element:
if you need to get value, use
HashMap
if just determine contain or not, use
HashSet
orboolean[]

Templates
BFS in a tree
Queue -> q.offer(root) -> while -> levelNum = q.size() -> for loop
if you don't need layer,
for loop
is not required.
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<TreeNode> q = new Queue<TreeNode>();
if (root == null) return res;
q.offer(root);
while (!q.isEmpty()) {
int levelNum = q.size();
List<Integer> tmpList = new ArrayList<Integer>();
for (int i = 0; i < levelNum; i++) {
TreeNode curr = q.poll();
tmpList.add(curr.val);
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
res.add(tmpList);
}
return res;
}
}
Permutation & Combination


Last updated
Was this helpful?