三分钟讲明白DFS(深度优先搜索)
稍微了解一点的人都知道，当我们需要从一个树结构中寻找到一些符合条件的元素时，我们都知道通过广度优先搜索或者深度优先搜索来有效地解决问题。那么具体是怎样一种手段去搜索呢？广度优先搜索(BFS)我们之前已经聊过了，现在我们就来谈谈深度优先搜索(DFS)。
DFS在某种程度上跟BFS很像，他们只是在侧重层级还是深度上有所区分。一般在做深度优先搜索的时候我们都选择使用递归的方式，除此外我们也可以像BFS一样使用辅助数据结构，比如说栈。所以通常我们的的深度优先搜索算法的空间复杂度都在O(H)，这个H指的是树的深度。
老规矩，我们先来看一道需要用深度优先搜索解决的简单算法题：给定一个二叉树和一个数字“S”，判断是否存在从根节点到叶节点这样一个路径，使得这个路径上所有节点的和等于S。
从根节点到叶节点，这是典型的DFS题目。为了找到这样的路径，我们只能挨个去遍历每个路径。
我们来思考下具体步骤：
从二叉树的根节点开始深度优先搜索。
如果当前节点不是叶节点，我们要做两件事。
用当前和减去当前节点的值来得到一个新的和=> `S = S - node.value`。
对当前节点两个子节点都分别做上面这一步。
每一步我们都要看当前节点是不是叶节点，它的值是不是等于当前的和，如果都满足，那我们找到了这样一个路径。
如果当前节点是个叶节点但是值跟当前和不相等，那gg。
整体思路就这么几步，思路想明白后，我们就可以来写解题代码了：
public static boolean hasPath(TreeNode root, int sum) {
if (root == null)
return false;
// 如果是叶节点并且值跟当前地sum相等，那就是找到了
if (root.val == sum && root.left == null && root.right == null)
return true;
// 分别对左节点跟右节点进行递归
return hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);
}
这样一个最基本的深度优先搜索就完成了！所以说树的搜索是我最喜欢做的题目类型之一，因为它真的简单啊！因为每个节点都要遍历到，一般没有什么花里胡哨的优化技巧，而且搜索又是固定的模板，甚至题目做多了之后一般的题目都可以无脑解。也因为我们要遍历所有的节点，我们的时间复杂度跟空间复杂度都在O(N)。
有了这些铺垫之后，我们已经对DFS有了一个大概的印象。基本上核心就是这个东西，我之前在讲其他套路时也说了，一定要抓住核心，根据核心我们就能判断用什么方法来解题。一般的题目都不会考得这么直接，但也都在核心之上加一些弯弯绕绕做一点限制，基于此，我们再来看一道稍微复杂一点的题：给定一个二叉树跟一个序列，判断在这个二叉树中这个序列是否以根节点到子节点的路径存在。
粗略一看，跟我们刚开始的题目似乎差不多。我们仍然可以用类似的深度优先搜索来处理，只不过有一个点要注意，我们得把当前节点跟这个序列对应的位置上的元素做一个匹配，只要有一个不匹配那我们就要pass掉一个路径。
那要追踪是否匹配也很简单，我们用一个变量记录一下当前匹配到序列的哪个位置，然后在每一步做个比较就好了：
public static boolean findPath(TreeNode root, int[] sequence) {
if (root == null)
return sequence.length == 0;
return findPathRecursive(root, sequence, 0);
}
private static boolean findPathRecursive(TreeNode currentNode, int[] sequence, int sequenceIndex) {
if (currentNode == null)
return false;
if (sequenceIndex >= sequence.length || currentNode.val != sequence[sequenceIndex])
return false;
// 如果是叶节点，并且也到了序列的最后一个数，那就是找到了
if (currentNode.left == null && currentNode.right == null && sequenceIndex == sequence.length - 1)
return true;
// 对左节点跟右节点做递归
// 有一个存在就行
return findPathRecursive(currentNode.left, sequence, sequenceIndex + 1)
|| findPathRecursive(currentNode.right, sequence, sequenceIndex + 1);
}
好了，我已经把DFS核心的思想尽可能简单地用两道中级算法题表达出来了。算法题它就是这样一个东西，循序渐进，题目都是由简单的基础演变得复杂，相应地，我们解题也可以在简单解法的上对特定的附加条件做特定的处理，一步一步发散自己的思路，一步一步向正解靠近。虽然不是DFS最困难的题目，但这里用来讲算法的概念刚刚好。算法的东西篇幅长了就很难继续看下去，所以困难的题型我们可以下次再一起来看。Happy coding～