vlambda博客
学习文章列表

三分钟讲明白DFS(深度优先搜索)

稍微了解一点的人都知道,当我们需要从一个树结构中寻找到一些符合条件的元素时,我们都知道通过广度优先搜索或者深度优先搜索来有效地解决问题。那么具体是怎样一种手段去搜索呢?广度优先搜索(BFS)我们之前已经聊过了,现在我们就来谈谈深度优先搜索(DFS)。

DFS在某种程度上跟BFS很像,他们只是在侧重层级还是深度上有所区分。一般在做深度优先搜索的时候我们都选择使用递归的方式,除此外我们也可以像BFS一样使用辅助数据结构,比如说栈。所以通常我们的的深度优先搜索算法的空间复杂度都在O(H),这个H指的是树的深度。

老规矩,我们先来看一道需要用深度优先搜索解决的简单算法题:给定一个二叉树和一个数字“S”,判断是否存在从根节点到叶节点这样一个路径,使得这个路径上所有节点的和等于S。

从根节点到叶节点,这是典型的DFS题目。为了找到这样的路径,我们只能挨个去遍历每个路径。

我们来思考下具体步骤:

  1. 从二叉树的根节点开始深度优先搜索。

  2. 如果当前节点不是叶节点,我们要做两件事。

    • 用当前和减去当前节点的值来得到一个新的和=> `S = S - node.value`。

    • 对当前节点两个子节点都分别做上面这一步。

  3. 每一步我们都要看当前节点是不是叶节点,它的值是不是等于当前的和,如果都满足,那我们找到了这样一个路径。

  4. 如果当前节点是个叶节点但是值跟当前和不相等,那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~