DFS V.S. BFS
DFS（Deep First Search）深度优先搜索：其实就是回溯算法
BFS（Breath First Search）广度优先搜索：把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，写BFS算法都是用「队列」，每次将一个节点周围的所有节点加入队列。
BFS相对DFS的最主要区别就是：BFS找到的路径一定是最短的，但代价就是空间复杂度比DFS大很多。
一、算法框架
BFS问题的本质就是让你在一幅「图」中找到起点 start 到终点 target 的最近距离。
广义的描述可以有各种变体：
走迷宫——有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？
单词转变——两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？
连连看——两个方块消除的条件不仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个团，游戏是如何判断它俩的最短连线有几个拐点的？
这些问题都没什么奇技淫巧，本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径。这就是BFS的本质，框架搞清楚了直接默写就好。记住下面的框架：
队列 q 就不说了，BFS的核心数据结构；cur.adj() 泛指 cur 相邻的节点，比如二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要visited。
二、二叉树的最小高度
LeetCode 111
显然起点就是 root，终点就是最靠近根节点的那个「叶子节点」，叶子节点就是两个子节点都是 null 的节点：
照这题的实际情况改写下框架：
二叉树是很简单的数据结构，其他复杂问题都是这个框架的变形。在探讨复杂问题之前，我们解答两个问题：
1. 为什么BFS可以找到最短距离，DFS不行吗？
首先我们看BFS的逻辑，depth每增加一次，队列中的所有节点都向前迈一步， 这保证了第一次到达终点的时候，走的步数是最少的。
DFS不能找最短路径吗？其实也是可以的，但是时间复杂度相对高很多。DFS实际上是靠递归的堆栈记录走过的路径，你要找到最短路径，肯定的吧二叉树中所有树杈都搜索玩才能对比出最短的路径有多长。而BFS借助队列做到一次一步「齐头并进」，可以在不遍历完整棵树的情况下找到最短距离。
DFS是线，单打独斗；BFS是面，集体行动。
2. 既生BFS，何生DFS？
BFS可以找到最短距离，但是空间复杂度高，而DFS的空间复杂度较低。
假设一颗满二叉树，节点为N，对于DFS算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，O(logN)。但是BFS算法队列中每次都会存储二叉树的一层节点，最坏情况是树的底层，节点数为N/2，时间复杂度为O(N)。
所以，BFS还是有代价的。一般来说在找最短路径的时候用BFS，其它时候还是DFS使用得多些。
三、解开密码锁的最少次数
LeetCode 752
这里start是 '0000'，target 是函数输入的，可以假设为'0202'。start 通过旋转4个拨轮到达target，一次只能拨一个。对于一个拨轮，可以往大数拨，可以往小拨，这是两种选择，而总共有四个旋钮，每个节点的下一步一共八种选择，相当于每个节点有8个向后相邻的节点。
有一个比较小的空间优化：可以不需要dead这个哈希集合，直接将这些元素初始化到 visited 集合中。
四、双向BFS优化
BFS算法还有一种稍微高级一点的优化思路：双向BFS，可以进一步提高算法的效率。
传统的BFS框架就是从起点开始向四周扩散，遇到终点时停止；而双向BFS则是从起点和终点同时开始扩散，当两边有交集的时候停止。
双向BFS单向只走二分之一的步数，并且能剪枝target方向的大部分节点。
不过，双向BFS也有局限，因为你必须知道终点在哪里。
二叉树的最小高度问题——不知道终点在哪，无法优化；
密码锁问题——知道终点，可以优化：
双向BFS还是遵顼BFS算法框架的，只是不再使用队列，而是使用HashSet方便快速判断两个集合是否有交集。
另外一个技巧点就是 while 循环的最后交换 q1 和 q2的内容，所以只要默认扩散 q1 就相当于轮流扩散 q1 和 q2 。
其实双向 BFS 还有一个优化，就是在while循环开始时做一个判断：
为什么这是一个优化呢？
因为按照BFS的逻辑，队列（集合）中的元素越多，扩散之后新的队列（集合）中的元素就越多；在双向BFS算法中，如果我们每次都选择一个较小的集合进行扩散，那么占用的空间增长速度就会慢一些，效率就会高一些。
