递归是一种解决问题的编程方法。通常，需要使用深度优先搜索算法（DFS）处理的问题，都可以使用递归的方法来处理。
进行递归求解，核心是递归函数的设计，本篇通过两个例子，来分析递归函数的设计方法。
1. 例子
1.1 重建二叉树
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
这道题的思路首先来源于对前序和中序遍历结果的结构的认识。
前序遍历：根结点 | 左子树 | 右子树
中序遍历：左子树 | 根结点 | 右子树
抽象一点的说，重建二叉树的过程为：找到根结点 以及左右子树。然后对于左右子树再分别重复操作：找到根结点及子树的左右子树。一直到子树只有一个结点为止。
根据上述陈述设计递归函数，需要的输入量包括：根结点在前序遍历中的位置；子树对应的结点在中序遍历中的范围-起始位和终止位。
递归函数设计
- 返回值：根结点。
- 输入：preorder 的中根结点的位置；inorder 中对应的结点范围（用于确定左子树的根结点和右子树的根结点）；
- 递归结束条件：inorder 中前后两个结点位置相同。以及当inorder的前位置位于后位置之后。
- 递归操作：（类似前序遍历）- 放置根结点；调用函数构建左子树；调用函数构建右子树。
特殊情况处理：
- 输入为空；
- 某个子树为空的情况；
下面为我的实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
private int[] porder;
private int[] iorder;
private Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.porder = preorder;
this.iorder = inorder;
if(preorder == null || preorder.length == 0) return null;
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return recursion(0,0,inorder.length -1);
}
private TreeNode recursion(int root, int inorderStart, int inorderEnd){
if(inorderEnd == inorderStart) return new TreeNode(porder[root]);
if(inorderStart > inorderEnd) return null;
TreeNode res = new TreeNode(porder[root]);
int tmp = map.get(porder[root]);
res.left = recursion(root+1, inorderStart, tmp-1);
res.right = recursion(root+tmp-inorderStart+1,tmp+1,inorderEnd);
return res;
}
}
|
补充：关于重建二叉树，中序遍历的结果是必须的，中序遍历可以和先序遍历或者后序遍历组合，重建出二叉树。
1.2 矩阵中的路径
LeetCode-剑指 Offer 12. 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
1
2
3
| [["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
|
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
这道题目使用深度优先搜索算法进行匹配字符串的搜索。实际上，深度优先的搜索算法一般都会用到递归来处理（二叉树的中序遍历，实际上可以看做是一种深度优先的搜索算法）。
同样的，任务就是设计这个递归函数：
- 返回值：boolean 值，是否存在。
- 输入参数：当前搜索点所在的位置。包括：在 待搜索矩阵中的位置 和 目标字符中的位置。
- 终止条件：成功匹配到目标 或者 搜索点超出矩阵范围。根据题目条件，如果当前元素已经访问过了-也需要终止
- 递归操作：匹配当前字符，不匹配，返回false，匹配，继续搜索上下左右。
注意事项：
- 终止条件不仅有过大超过边界，还有小于0 的情况，也是超过了边界，需要捕捉；
- 终止条件：成功捕获到目标要放在最上边！不然
return false 那句会出现数组越界的问题；
- 需要注意，题目没有规定从0开始遍历。所以要在主程序段添加一个对数组的二重遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
private char[][] board;
private char[] wordChar;
public boolean exist(char[][] board, String word) {
char[] wordChar = word.toCharArray();
this.board = board;
this.wordChar = wordChar;
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(dfs(i,j,0)) return true;
}
}
return false;
}
private boolean dfs(int rowIndex, int colIndex, int wordIndex){
if(wordIndex == wordChar.length) return true;
if(rowIndex >= board.length || rowIndex < 0
||colIndex >= board[0].length || colIndex < 0
||board[rowIndex][colIndex] != wordChar[wordIndex]) return false;
board[rowIndex][colIndex] = '\0';
boolean res = dfs(rowIndex+1,colIndex,wordIndex+1)
||dfs(rowIndex,colIndex+1,wordIndex+1)
||dfs(rowIndex,colIndex-1,wordIndex+1)
||dfs(rowIndex-1,colIndex,wordIndex+1);
board[rowIndex][colIndex] = wordChar[wordIndex];
return res;
}
}
|