深度优先搜索算法

基本概念

DFS是 深度优先搜索算法 的简称，和 宽度优先搜索算法 类似，都是一种遍历搜索的算法，两者通常解决需要最优路径的题，这样就需要遍历每一条路径才能或取到最优路径。

一般BFS对应着队列这种数据结构，而DFS就对应着栈这种数据结构（一般使用DFS就不会直接显示声明栈，而是写成递归的方式，而这种递归调用函数称为调用栈）

在大多数情况下，我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别：遍历顺序。

与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。

代码模板

这个代码模板很宽泛，也可以参考一下自顶向下的实现方式和自底向上的实现方式的代码模板。

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

中文化就是：

/*
 * 然会真表示有一条路径可以到达目标结点
 */
boolean DFS(现在执行操作的节点，目标节点，记录被遍历过节点的数据结构) {
    return true 当 现在执行操作的节点 就是 目标节点；
        
    // 如果前面没有返回，执行到了这一步就表示当前这个节点就不是目标节点，就需要找到新的结点
    for(下一个想要去的节点 : 每一个可以去的结点（一般是当前结点的周围的结点）) {
        if(下一个想要去的结点 不在 记录被遍历过节点的数据结构（没有去过）){
            先将 下一个想要去的结点 添加进 记录被遍历过节点的数据结构 中；
            return DFS(下一个想要去的结点, 目标节点, 记录被遍历过节点的数据结构)
        }
    }
    return false;
}

这种表述方式是建立在路劲是否可通上面的，但是对于数字上也可以（判断这条路径上的数字和是否可以等于某个值）。

参数

现在执行操作的节点

这个参数一般都是会有的，只是在不同的题目中可能不同而已。

如果是在这种路径式的题目中，就是说的结点，或者就是数组的下标。

如果是判断数据和子类的题目可能就是当前的层数，或者当前的答案结果数。

目标节点

这个参数其实不一定要有。

对于有目标值，或者数组的目标下标的题目中可能需要有。

如果是求路径最大和或最小和时可能会有这个参数，但是这种题一般都是用DP做，所以这个参数其实用的不多。

记录被遍历过节点的数据结构

这个参数一般是需要的。

不过为了简便其实一般是可以作为全局变量设置在外面的。

对于树这种题目来说其实就不需要这个参数，因为树的遍历一般都不会重复，且能够知道去过的点。

自顶向下的实现方式

“自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。 所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。

相当于是先计算值，再将值交给 下一个想要去的节点 ，再让它计算，再传给下一个这样。就是由上面将值或其他数据作为参数传递给 下一个想要去的节点 ，一般答案出现在最后一个节点（在树中就是叶子节点）。当然也要视情况决定是否要有个数据记录最终答案。因为这中自顶向下的实现方式一般是无返回的，需要全局变量来接收这个值（全局变量也需要比较最优的结果）。

代码模板

private Tpye answer;		// 记录结果的全局变量
private void DFS(Node cur, Type ans, Set<Node> visited) {
    if (cur not satisfy requirement) {
        return;// 这个点如果不满足继续走下去的要求就结束这条路，返回回去就会走下一条路
    }
    if (cur have not neighbor) { // 如果走到头了（到叶子节点了）
        // 比较得出最优答案
        if ans is better than answer:
        	answer = ans;
    }
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            DFS(next, ans+cur.val, visited);// 经过了现在的节点，传给下一个节点的参数值需要变化，视情况变化
        }
    }
}

自底向上的实现方式

“自底向上” 是另一种递归方法。 在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。 这个过程可以看作是后序遍历的一种。

就是说要先走到最底层然后依靠最底层逐渐向上返回值，然后上层拿到这个返回值之和再操作。例如比较多个返回值，取最优，然后将最优的值往上传，或其他情况。一般是不需要自顶向下中的全局变量来接收结果，因为函数的返回值往往就是结果，也不需要向下传递的参数。

代码模板

public Type DFS(Node cur, Set<Node> visited) {
	if (cur not satisfy requirement) {
        return 0;// 这个点如果不满足继续走下去的要求就结束这条路，返回回去就会走下一条路,返回值要视情况
    }
    List<Type> list = ArrayList<>();
	for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            list.add(DFS(next, visited));// 接收每一个下面返回的值,如果可以直接判断就可以省去存储值的数据结构
        }
    }
    // 根据众多的返回值得到最优的返回值，大多数题都不会这么麻烦
    Type answer = list.get(0);
    for(ans : each value of list){
        if ans is better than answer:
        	answer = ans;
    }
	return answer;	// 返回这一层的结果给上一层
}

例题

原题连接

二叉树的最大深度 力扣104

题目

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

自顶向下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int answer;// 全局变量接收结果
    public int maxDepth(TreeNode root) {
        DFS(root,1);
        return answer;
    }

    public void DFS(TreeNode root,int ans) {
        if(root == null) {// 不满足条件的情况，需要结束再往下走了
            return;
        }
        if(root.left == null && root.right == null) {// 如果是叶子节点，没有可以再走的路
            answer = Math.max(answer,ans);// 比较最好的结果
        }
        // 其他题就是遍历接下来可以走的点，但是对于二叉树来所就是走左右，如果是N叉树来所就需要遍历
        DFS(root.left,ans+1);// 接下来再走左边
        DFS(root.right,ans+1);// 接下来再有右边
    }
}

其他例题

皇后问题

按照国际象棋中的皇后吃法进行摆放，求出有n个皇后，摆放到n乘n的棋盘上，彼此不能吃掉对方的摆放方法。

• 输入格式

  n

• 输出格式

  每一个答案 n 行，每一行一个Q表示皇后位置，其他位置为 ‘.’。

  答案间输出一行空格。

数据范围： 1 <= n <= 9

代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 10;
int n;		// 皇后个数
int q[N];	// 存储皇后位置

void dfs(int p) {
	if (p == n) { 							// 输出
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (q[i] == j) cout << 'Q';
				else cout << '.';
				cout << ' ';
			}
			cout << endl;
		}
		cout << endl;
		return;
	}
	int j;
	for (int i = 0; i < n; ++i) {
		j = 0;
		for (;j < p; ++j) {
			if (q[j] == i) break;					// 不在同一列
			if (abs(q[j] - i) == abs(p - j)) break; // 不在同一对角线
		}
		if (j == p) {
			q[p] = i;
			dfs(p+1);
		}
	}
}

int main () {
	cin >> n;
	dfs(0);
	return 0;
}

排列数字

这个就是经典的全排列问题

给定一个整数n，将数字1-n排列成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。

• 输入格式

  共一行，包含一个整数n

• 输出格式

  按字典序输出所有排列方案，每个方案占一行。

示例

• 输入：

  3

• 输出：

  1 2 3

  1 3 2

  2 1 3

  2 3 1

  3 1 2

  3 2 1

思路

DFS主要考虑的点是顺序。

如果 n = 3。则有三个空位。从 1 开始填。第一位有三种填法对应三种分支。

代码

#include <iostream>

using namespace std;

const int N = 10;    // 数组的最大容量

int n;               // 全排列的个数
int path[N];		 // 存储答案的数组
bool st[N];			 // 记录某数字是否被使用的数组

void dfs(int p) {
	if (p == n) {
		for (int i = 0; i < n; ++i) 
			cout << path[i] << " ";
		cout << endl; 
		return;
	}
	for (int i = 1; i <= n; ++i) {
		if(!st[i]){
			path[p] = i;	// 存储方案
			st[i] = true;	// i已被使用
			dfs(p+1);		// 找下一层
			st[i] = false;  // 回溯，恢复原样 
		}
	}
}

int main() {
	cin >> n;
	dfs(0);
	return 0;
} 

外观数列

原题连接：38. 外观数列

---

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

---

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221”
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 “3322251” 的描述如下图：

示例 1：

输入：n = 1
输出：”1”
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出：”1211”
解释：
countAndSay(1) = “1”
countAndSay(2) = 读 “1” = 一 个 1 = “11”
countAndSay(3) = 读 “11” = 二 个 1 = “21”
countAndSay(4) = 读 “21” = 一 个 2 + 一 个 1 = “12” + “11” = “1211”

代码

就是暴力递归

class Solution {
    public String countAndSay(int n) {
        String str = "1";
        return fun(str,--n);
    }

    public String fun(String str,int n){
        if(n == 0){
            return str;
        }
        StringBuilder sb = new StringBuilder();
        int x = 1;
        int index = 0;
        while(index < str.length()){
            if(index < str.length() - 1 && str.charAt(index) == str.charAt(index+1)){
                x++;
            } else {
                sb.append(Integer.toString(x) + str.charAt(index));
                x = 1;
            }
            index++;
        }
        str = fun(sb.toString(),--n);
        return str;
    }
}

被围绕的区域

原题链接：130. 被围绕的区域

---

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

---

示例 1：

输入：board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]
输出：[[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [[“X”]]
输出：[[“X”]]

代码

这道题需要冲边界开始搜索，如果该边界是’O’，那么从这个’O’开始走。要求是不越界，不是’X’，没有走过。满足要求就先替换成另外一个字母(代表走过了)，最后统一换成只有’X’和’O’的矩阵。

class Solution {
    int[] x = {1,-1,0,0};
    int[] y = {0,0,1,-1};
    int row;
    int col;

    public void solve(char[][] board) {
        row = board.length;
        col = board[0].length;
        
        for(int i = 0 ; i < col ; i++){
            if(board[0][i] == 'O') {
                change(0,i,board);
            }
            if(board[row - 1][i] == 'O') {
                change(row-1,i,board);
            }
        }
        for(int i = 0 ; i < row ; i++){
            if(board[i][0] == 'O') {
                change(i,0,board);
            }
            if(board[i][col-1] == 'O') {
                change(i,col-1,board);
            }
        }
        for(int i = 0 ; i < row ; i++){
            for(int j = 0; j < col ; j++){
                if(board[i][j] == 'A') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }
    }

    public void change(int i,int j,char[][] board) {
        board[i][j] = 'A';
        for(int k = 0 ; k < 4 ;k++){
            if(i+x[k] < row && i+x[k] > 0 && j + y[k] < col && j + y[k] > 0){
                if(board[i + x[k]][j + y[k]] == 'O') {
                    change(i+x[k],j+y[k],board);
                }
            }
        }
    }
}

在二叉树中增加一行

原题链接：623. 在二叉树中增加一行

---

给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。

注意，根节点 root 位于深度 1 。

加法规则如下:

给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
cur 原来的左子树应该是新的左子树根的左子树。
cur 原来的右子树应该是新的右子树根的右子树。
如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。

---

示例 1:

输入: root = [4,2,6,3,1,5], val = 1, depth = 2
输出: [4,1,1,2,null,null,6,3,1,5]

示例 2:

输入: root = [4,2,null,3,1], val = 1, depth = 3
输出: [4,2,null,1,1,3,null,null,1]

代码

深度优先搜索：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (root == null) {
            return null;
        }
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        if (depth == 2) {
            root.left = new TreeNode(val, root.left, null);
            root.right = new TreeNode(val, null, root.right);
        } else {
            root.left = addOneRow(root.left, val, depth - 1);
            root.right = addOneRow(root.right, val, depth - 1);
        }
        return root;
    }
}