DFS 算法模板

DFS总结：
1、第一次讲的dfs模板一定要记住。
2、二叉树的遍历，https://www.cnblogs.com/rnanprince/p/11595380.html，先序中序的递归和迭代写法必须掌握，像算法模板一样记住。后序遍历只掌握递归写法。
3、遍历过程中需要记住上次遍历节点才能得到结果的，记住模板。
last_node = None
def dfs  (root):
   if last_node is None:
	last_node = root
   else:
     compare(last_node, root)....
	 last_node = root
   dfs(root.left)
   dfs(root.right)
4、BST的搜索代码要会，要记住。
5、排列组合类题目：
组合类算法，都使用分治+递归的思路去写，重复元素，先排序，无非多了一个判断。
排列类算法，用交换思路，都使用分治+递归的思路去写，重复元素，无非多了一个判断。
6、隐式图搜索:八皇后，正则表达式匹配，word拼图

i        j
|        | 
abc  ==> abc   dfs(i+1, j+1)
a*bc ==> aaabc dfs(i+2, j) or dfs(i, j+1)
a.bc ==> adbc  dfs(i+1, j+1) 


  a b c
  g a n
  a x x
  i x x
  n x x
dfs(左边走)
dfs(右边走)
dfs(上边走)
dfs(下边走)
走的过程中将路径记下来

7、常见问题：
  超时的处理：剪枝（cache、trie去剪枝），修改算法bfs，用dp
  测试用例过不完：自己debug，放到ide去调试