算法思路：
图用邻接表为输入，思路递归实现, 还要一个机制记录节点访问过没有，可以用HashSet，同时它作为结果存储BFS访问结果。
BFS多用于找最短路径
DFS多用于快速发现底部节点和具体路劲问题（如路径和或打印路径）。
BFS优缺点： 同一层的所有节点都会加入队列，所以耗用大量空间 仅能非递归实现 相比DFS较快，空间换时间 适合广度大的图
DFS优缺点： 无论是系统栈还是用户栈保存的节点数都只是树的深度，所以空间耗用小 有递归和非递归实现 由于有大量栈操作（特别是递归实现时候的系统调用），执行速度较BFS慢 适合深度大的图
如果BFS和DFS都可以用，建议用BFS，因为工业应用中，BFS不用有限的栈空间，可以利用到所有内存。
图DFS
算法步骤：
- 不合法情况（已访问、越界、trivial情况等）返回。
- 标记为已访问。
- 递归访问相邻节点。
- DFS路径尽量记录在数组中而非ArrayList中，路径(图)再DFS后要恢复为原状态L332。
Python代码：
1
2
3
4
5
6
7def dfs(self, graph, start, visited, res):
if start in visited:
return
visited.add(start)
res.append(start)
for node in graph[start]:
self.dfs(graph, visited, node, res)
字符型DFS/组合
跟填位法相同的地方：
- 终止条件一样len(path)==TARGET, res.append(list(path)), return
- API一样：dfs(nums, start, path, result, visited[optional]), 4个参数 不同的是，组合模板是的下一轮递归用i + 1, 但这里由于是填位，一位一位加入，所以是start + 1
注意事项：
- 输入值为空的情况或空节点
- 求得解以后复制path到result中
- 终止条件记得return
- 每次递归完恢复输入图或中间结果path的状态，递归式用i + 1
Python代码：
1
2
3
4
5
6
7
8def dfs(self, input, start, TARGET, path, result):
if len(path) == TARGET:
result.append(list(path))
return
for i in <func>(input[start]):
path.append(i)
self.dfs(input, i + 1, TARGET , path, result)
path.pop()
例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# char dfs (type 2 linear) Leetcode 77 Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]
def combine(self, n: int, k: int) -> List[List[int]]:
nums = [i + 1 for i in range(n)]
path, res = [], []
self.dfs2(nums, 0, k, [], res)
return res
def dfs2(self, nums, start, k, path, res):
if len(path) == k:
res.append(list(path))
return
for i in range(start, len(nums)):
path.append(nums[i])
self.dfs2(nums, i + 1, k, path, res)
path.pop()
填位法
跟字符型DFS/组合相同的地方：
- 终止条件一样len(path)==TARGET, res.append(list(path)), return
- API一样：dfs(nums, start, path, result, visited[optional]), 4个参数 不同的是，组合模板是的下一轮递归用i + 1, 但这里由于是填位，一位一位加入，所以是start + 1
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12def dfs(self, n, start, path, res, col_set):
if len(path) == TARGET:
res.append(list(path))
return
for i in range(n):
if not self.is_valid(start, i, col_set):
continue
path.append(i)
col_set.add(i)
self.dfs(n, start + 1, path, res, col_set)
col_set.remove(i)
path.pop()
例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17# filling dfs (type 3) LeetCode 017 Letter Combinations of a Phone Number
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
path, res = [], []
self.dfs3(digits, 0, path, res)
return res
def dfs3(self, digits, start, path, res):
if len(path) == len(digits): # len(path) == TARGET
res.append("".join(path))
return
keys = DIGIT2CHAR[digits[start]]
for letter in keys:
path.append(letter)
self.dfs3(digits, start + 1, path, res) # remember start + 1
path.pop()
Catalan法(双边递归)
DFS中几乎是最难的类型。考得很少。主要思想是左右儿子递归结果叉乘，再将所有结果返回。所以返回值一定是list
注意事项：
- 返回结果是解的集合，所以终止条件返回也需要是一个list
- 循环中除掉自己，递归左部分和右半部分，叉乘它们的结果
- 与记忆性搜索的模板类似，有时需要和它一起用，见LeetCode 241 Different Ways to Add Parentheses
Python代码：
1
2
3
4
5
6
7
8
9def dfs(self, input):
if <终止条件>:
return [] # remember to use list
res = []
for i in range(len(input)):
left_res = self.dfs(input[:i])
right_res = self.dfs(input[i + 1:])
res += [<calculate results> for _l in left_res for _r in right_res]
return res
时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)
记忆性搜索(单边Catalan)
见记忆性搜索
例子：
LeetCode 140 Word Break II
这是单边catalan
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
wordSet = set()
for word in wordDict:
wordSet.add(word)
cache = {}
res = self.dfs(s, wordSet, cache)
return [] if len(res) == 1 and not res[0] else res
def dfs(self, s, wordSet, cache):
if not s:
return ['']
if s in cache:
return cache[s]
res = []
for i in range(len(s)):
if s[:i + 1] not in wordSet:
continue
li = self.dfs(s[i + 1:], wordSet, cache)
for ss in li:
res.append((s[:i + 1] + ' ' + ss).strip())
cache[s] = res
return res
例子：
返回结果是解的集合，所以终止条件返回也需要是一个[None]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# catelan dfs (type 4) LeetCode 095 Unique Binary Search Trees II
# return the root of all the possible trees
def generateTrees(self, n: int) -> List[TreeNode]:
nums = [_ + 1 for _ in range(n)]
return self.dfs4(nums, 0, n)
def dfs4(self, nums, start, end): # [start, end)
if start >= end:
return [None] # remember becaues we want the 2 for-loop happen
res = []
for i in range(start, end):
left_root_nodes = self.dfs4(nums, start, i) # 0, 0
right_root_nodes = self.dfs4(nums, i + 1, end) # 1, 1
for left_root_node in left_root_nodes:
for right_root_node in right_root_nodes:
node = TreeNode(nums[i])
node.left = left_root_node
node.right = right_root_node
res.append(node)
return res
应用题型：
LeetCode 095 Unique Binary Search Trees II
LeetCode 241 Different Ways to Add Parentheses
LeetCode 761 Special Binary String
Java代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/*
* graph: 邻接表
* visited: 记录已访问节点，避免重复访问
* start: DFS的根节点
*/
public void dfs(HashMap<Integer, LinkedList<Integer>> graph, HashSet<Integer> visited, int start){
if(visited.contains(start)){
return;
}
visited.add(start);
System.out.print(start+",");
for(Integer child : graph.get(start)){
dfs(graph, visited, child);
}
}
算法分析：
时间复杂度为O(n)，h为树的高度，空间复杂度O(h)，如果用系统栈，可理解其为O(1)。
