DFS && BFS

DFS和BFS都可以对空间进行遍历
BFS ：“最短路” 第一次搜到的点是离根点最近的点

DFS vs BFS
      数据结构    空间
DFS ： stack       O(h)
BFS ： queue      O(2^h)

DFS
尽可能往深搜 回溯 剪枝

dfs的问题一般不需要讨论时间复杂度问题，因为大多数的情况下都不会达到最坏的情况，而且我们也可以对dfs的过程中进行优化。

比如LC上的这道题，我们先进行了BFS计算出最短路，然后再去dfs搜索。
LeetCode 126. 单词接龙 II

题解

其它例题：

LeetCode 78. 子集
LeetCode 79. 单词搜索
LeetCode 113. 路径总和 II
LeetCode 112. 路径总和
LeetCode 110. 平衡二叉树
LeetCode 111. 二叉树的最小深度
LeetCode 126. 单词接龙 II
LeetCode 129. 求根节点到叶节点数字之和
LeetCode 130. 被围绕的区域
LeetCode 131. 分割回文串

BFS(边的权重必须是1或者相等)

可以搜到最短
首先搜到距离为1的点 然后是距离为2的点 …
尽可能往宽了搜 最少几次 最短距离…这些问题

BFS 框架：

while( queue 不空){
	t <- 队头
	拓展 t
	//如果想要记录路径，在这里使用当前的xy记录上一个点
	//定义一个pair 比当前在 （4,5）点，从 (4,4)过来的
	//那么就是Prev(4,5)=make_pair(4,4)，
	//最后倒着输出一遍就可以输出路径 从n-1 m-1
}

其它例题：

LeetCode 102. 二叉树的层序遍历
LeetCode 103. 二叉树的锯齿形层序遍历
LeetCode 108. 将有序数组转换为二叉搜索树
LeetCode 127. 单词接龙
LeetCode 126. 单词接龙 II