DFS 解题模式

概述
这篇文章介绍如何解决 Leetcode 常见的 DFS 问题的模式，了解这个基本模式之后，相信面对大部分 DFS 问题（如果 hard 难度的需要一些变形）都能够迎刃而解。阅读之前希望你对图的基础知识有一定的了解，例如什么是图，常见的图有那些，如何遍历图，Leetcode 上 DFS 问题常见的都是无环图，所以我们这里也只讨论无环图的解法。

辨别问题


那么什么样的问题可以用 DFS 来解决呢？在 Leetcode 中，DFS 问题常见的表达形式为：

“给定一个图（树，字符串，矩阵），找到在遍历图的过程中，符合特定条件的数值或路径。”

（这里我把返回布尔值当成返回默认值或空路径的特殊情况），上面的这个定义有点抽象，举两个例子：

Leetcode 113 Path Sum II

    "Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum."

    “给定一个有向无环图（非空二叉树），找到在遍历图的过程中，符合特定条件的数值（路径和等于 sum ）”

        Given the below binary tree and sum = 22,

        input:

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

        output:

        [
            [5,4,11,2],
            [5,8,4,5]
        ]

Leetcode 200 Number of Islands

    Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

    “给定一个无向无环图（矩阵），找到在遍历图的过程中，符合特定条件的数值（岛的数量）”

        Input:
        11110
        11010
        11000
        00000

        Output: 1

解题模式
很多 DFS 问题可以用 DP 来解决，通常效率也会更高。不过 DP 的状态转移方程有时候不好想，那么这时候即使头脑空白也能遵循一个固定的思路，首先实现 DFS 的解法然后优化成 DP，首先我们先描述算法中要做的事情。

1. 遍历图

    如果题目要求返回的只是布尔值的话，遍历可以提早结束，不然遍历目标都是遍历整个图，若根节点不能访问所有其他节点，**那么就需要对每个节点进行 DFS 遍历**。

2. DFS 函数

    这个函数是一个递归函数，里面包含了 **is_valid** 以及 **match** 两个子函数。分别用作判断子节点是否合法，以及当前状态是否符合条件。

3. 返回结果


具体实现


1. 遍历图

注意这里我把 is_valid 的状态判断放到了 DFS 的子节点遍历中，所以主函数需要处理一些边界条件

   1. 从根节点可以访问所有其他节点（例子 1）：

1.         function main_function(graph):
   
2.             # 边界条件，例如如果图是空的，或者根节点本身就符合条件
   
3.             if not graph:
   
4.                 return []
   
5.             # 如果需要返回数值则创建变量（例如最大值，最小值），返回路径则创建数组：
   
6.             res = val // list[]
   
7.             element = first element in the graph
   
8.             # 对根节点进行 DFS 遍历
   
9.             dfs(element, res)
   
10.             return res

复制代码

   2. 根节点不能访问其他所有节点（例子 2)：

1.         function main_function(graph):
   
2.             # 边界条件，例如如果图是空的，或者根节点本身就符合条件
   
3.             if not graph:
   
4.                 return []
   
5.             res = val // list[]
   
6.             # 对图里面每个元素进行 DFS 遍历
   
7.             for element in the matrix:
   
8.                 dfs(element, res)
   
9.             return res

复制代码

   3. 如果题目要求的返回值是布尔值的话，遍历图可以提前结束：

1.         function main_function(graph):
   
2.             res = val // list[]
   
3.             for in the graph:
   
4.                 if dfs(element, res) is True:
   
5.                     return True
   
6.             return False

复制代码

2. DFS 递归函数

    1. 找到需要遍历的子节点

        遍历的子节点有时候不好找，对于有向图来说，树结构通常是它的子树节点，字符串根据实际情况可以是其他任意一个字符。无向图如某些矩阵则可能是上下左右节点，或者下右节点，这些看题目要求，同时因为要防止重复遍历，所以这里可以使用一个小技巧，把当前节点的值设为无效，DFS 遍历结束再还原。（下面的可选 2），函数中的的 **is_valid** 和 **match** 都是子函数

    2. 函数实现

        这里有四个重点，**1. 防止点被重复遍历**，**2. 检查节点是否合法**，**3. 检查更新后的状态是否符合要求**，**4. 更新接下来 DFS 的参数**。形式一我们把 match 函数放在子节点的遍历中，这样速度相对比较快，不过主函数需要处理边界情况。形式二则把 match 函数放在 DFS 函数的开头，虽然速度较慢，但是容易实现：

1. function dfs_first(element, res, current, target, path):
   
2.                 # 输入参数中，
   
3.                 # element 代表需要遍历的节点
   
4.                 # res 代表保存结果的最终容器
   
5.                 # current 代表当前状态（可选）
   
6.                 # target 代表目标状态
   
7.                 # path 代表遍历路径（可选）
   
8.                
   
9.                 # 遍历每一个子节点
   
10.                 for each child in element:
    
11.                     # 1. 修改图的节点值为非法（可选）
    
12.                     graph->val = unvalid value
    
13.                     # 2. 检查子节点是否合法，是否已经访问过，是否越界
    
14.                     if is_valid(child):
    
15.                         # 3. 检查子节点与元素组成的新状态是否符合条件
    
16.                         if match(current, child, target):
    
17.                             # 更新最终结果
    
18.                             res += new_res
    
19.                         else:
    
20.                             # 4. 遍历所有合法子节点，更新状态
    
21.                             dfs_first(child, res, current+child.val, target, path+child)
    
22.                     # 恢复图的节点值（可选）
    
23.                     graph->val = valid value
    
24. 
    
25.             function dfs_second(element, res, current, target, path):
    
26.                 # 输入参数中，
    
27.                 # element 代表需要遍历的节点
    
28.                 # res 代表保存结果的最终容器
    
29.                 # current 代表当前状态（可选）
    
30.                 # target 代表目标状态
    
31.                 # path 代表遍历路径（可选）
    
32. 
    
33.                 # 如果当前节点符合条件
    
34.                 if match(current, element, target):
    
35.                     # 更新最终结果
    
36.                     res += new_res
    
37.                     return
    
38.                 # 遍历每一个子节点
    
39.                 for each child in element:
    
40.                     # 1. 修改图的节点值为非法（可选）
    
41.                     graph->val = unvalid value
    
42.                     # 2. 检查子节点是否合法，是否已经访问过，是否越界
    
43.                     if is_valid(child):
    
44.                         # 4. 遍历所有合法子节点，更新状态
    
45.                         dfs_first(child, res, current+child.val, target, path+child)
    
46.                     # 恢复图的节点值（可选）
    
47.                     graph->val = valid value
    
48.                     
    
49.             function is_valid(child):
    
50.                 # 如果 child 合法则返回真，否则返回假
    
51.                
    
52.             function match(current, child, target):
    
53.                 # 如果当前 child 与 current 的组合满足题目与 target 的要求，则返回真

复制代码

原题分析

按照此解题模式，第一个例子可以这样实现：（形式一，Python 代码）

1.     class Solution:
   
2.         def pathSum(self, root, sum):
   
3.             # 边界情况
   
4.             if not root:
   
5.                 return []
   
6.             # 边界情况2，因为我们是在遍历中验证是否符合条件，所以这里要处理另外一个边界情况
   
7.             if root.val == sum and not root.left and not root.right:
   
8.                 return [[root.val]]
   
9.             # 因为根节点可以访问所有子节点，所以只需要遍历根节点
   
10.             return self.dfs(root, [], root.val, sum, [root.val])
    
11. 
    
12.         def dfs(self, node, res, current, target, path):
    
13.             # 遍历每一个子节点
    
14.             for n in [node.left, node.right]:
    
15.                 # 检查子节点是否合法，是否已经访问过，是否越界
    
16.                 if self.is_valid(n):
    
17.                     # 检查子节点与元素组成的新状态是否符合条件
    
18.                     if self.match(current, n, target):
    
19.                         # 更新最终结果
    
20.                         res.append(path+[n.val])
    
21.                     else:
    
22.                         # 遍历所有合法子节点，更新状态
    
23.                         self.dfs(n, res, current+n.val, target, path+[n.val])
    
24.             return res
    
25. 
    
26.         def is_valid(self, node):
    
27.             # 子节点在不同的 path 中可以重复遍历，所以只要存在则返回真
    
28.             if node:
    
29.                 return True
    
30.             return False
    
31.             
    
32.         def match(self, current, child, target):
    
33.             # 题目要求 child 必须为叶子节点，并且与之前值的和等于 target
    
34.             if not child.left and not child.right and current + child.val == target:
    
35.                 return True
    
36.             return False

复制代码

第二题也是类似的方法，形式一以及形式二都能实现，这里我选择了另一种特殊的方式，把 match 函数提前。

1.     class Solution:
   
2.         def numIslands(self, grid):
   
3.             # 边界情况
   
4.             if not grid:
   
5.                 return 0
   
6.             count = 0
   
7.             # 因为岛之间可能并不相连，所以需要遍历整个图
   
8.             for i in range(len(grid)):
   
9.                 for j in range(len(grid[0])):
   
10.                     # match 函数
    
11.                     if grid[i][j] == '1':
    
12.                         grid[i][j] = '#'
    
13.                         self.dfs(grid, i, j)
    
14.                         count += 1
    
15.             return count
    
16. 
    
17.         def dfs(self, grid, i, j):
    
18.             # 遍历可能的子节点
    
19.             for k, v in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
    
20.                 if self.is_valid(k, v, grid):
    
21.                     # 我把 match 函数抽离出来放在主函数中了，
    
22.                     # 这里也可以使用 match 函数的形式，即当周围节点都不为 1 的时候， count 增加 1
    
23.                     grid[k][v] = '#'
    
24.                     self.dfs(grid, k, v)
    
25.    
    
26.         def is_valid(self, i, j, grid):
    
27.             # 如果 i，j 合法的话
    
28.             if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
    
29.                 return False
    
30.             return True

复制代码

总结
解决 DFS 问题最重要的是四点，**1. 防止点被重复遍历**，**2. 检查节点是否合法**，**3. 检查更新后的状态是否符合要求**，**4. 更新接下来 DFS 的参数**，只要按照这个思路，形式怎么写都没关系。

真的感谢楼主，这段时间正好在攻dfs和bfs

谢谢分享👍

WIwindson 发表于 2019-7-2 22:56
我是从markdown转过来的，格式可能有点问题。同时希望大家给点建议 ：D

非常实用！楼主是否介意把markdown放到gist上面？论坛的排版实在有点捉急哈哈

我是从markdown转过来的，格式可能有点问题。同时希望大家给点建议 ：D

谢谢分享啊！

谢谢分享

不错的文章，谢谢分享！

思路很清晰，感谢楼主分享！

不错的文章 多谢分享

谢谢楼主分享！

感谢！刚好需要这个！