提示：Flood 是「洪水」的意思，Flood Fill 直译是「泛洪填充」的意思，体现了洪水能够从一点开始，迅速填满当前位置附近的地势低的区域。类似的应用还有：PS 软件中的「点一下把这一片区域的颜色都替换掉」，扫雷游戏「点一下打开一大片没有雷的区域」。
下面这几个问题，思想不难，但是初学的时候代码很不容易写对，并且也很难调试。我们的建议是多写几遍，忘记了就再写一次，参考规范的编写实现（设置 visited 数组，设置方向数组，抽取私有方法），把代码写对。
说明：以下问题都不建议修改输入数据，设置 visited 数组是标准的做法。可能会遇到参数很多，是不是都可以写成成员变量的问题，面试中拿不准的记得问一下面试官
733. 图像渲染（Flood Fill，中等） 200. 岛屿数量（中等） 130. 被围绕的区域（中等） 79. 单词搜索（中等） 题型三：字符串中的回溯问题提示：字符串的问题的特殊之处在于，字符串的拼接生成新对象，因此在这一类问题上没有显示「回溯」的过程，但是如果使用 StringBuilder 拼接字符串就另当别论。
在这里把它们单独作为一个题型，是希望朋友们能够注意到这个非常细节的地方。
回溯算法是早期简单的人工智能，有些教程把回溯叫做暴力搜索，但回溯没有那么暴力，回溯是有方向地搜索。「力扣」上有一些简单的游戏类问题，解决它们有一定的难度，大家可以尝试一下。
（欢迎大家补充。）
51. N 皇后（困难）：其实就是全排列问题，注意设计清楚状态变量，在遍历的时候需要记住一些信息，空间换时间； 37. 解数独（困难）：思路同「N 皇后问题」； 488. 祖玛游戏（困难） 529. 扫雷游戏（困难） 回溯嵌套有时候我们可能需要嵌套循环遍历一棵树，对每一个节点都做一遍前序遍历。所以这也是一种我们需要灵活应用的技巧。
面试题 04.12. 求和路径给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: 3 解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7] 答案一 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int res = 0; // 一重遍历 public int pathSum(TreeNode root, int sum) { if (root == null) { return 0; } f(root, sum); pathSum(root.left, sum); pathSum(root.right, sum); return res; } // 二重遍历 public void f(TreeNode root, int sum) { if (root == null) { return; } sum -= root.val; if (sum == 0) { res++; } f(root.left, sum); f(root.right, sum); } } 答案二 class Solution { public int pathSum(TreeNode root, int sum) { if (root == null) { return 0; } return f(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum); } private int f(TreeNode root, int sum) { if (root == null) { return 0; } int res = sum == root.val ? 1 : 0; // 判断当前节点值是不是目标和 sum -= root.val; return res + f(root.left, sum) + f(root.right, sum); } } 实例 凑算式这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
答案：
// 凑算式 public class Sy1 { public static void main(String[] args) { // TODO Auto-generated method stub choose(1); System.out.println("一共"+sum+"种解法"); } public static int sum = 0; // 用来存放总共的解法数 public static double[] a = new double[10]; // 判断数组里前j个元素是否与t相同 /** * @param a 传入一个数组a * @param j 判断前j个元素 * @param t 是否与t相同 * @return */ public static boolean same(double[] a, int j, int t) { for (int i = 1; i < j; i++) { if (a[i] == t) { return true; } } return false; } /** * @param a 判断a数组是否满足表达式 * @return 如果满足就true，不满足就false */ public static boolean expression(double[] a) { if ((a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]) == 10)) return true; else return false; } /** * @param i 选择第i个数字 递归 */ public static void choose(int i) { // 如果选择的数字大于9，则代表1~9均已选完，输出选择的表达式 if (i > 9) { if (expression(a)) { for (int x = 1; x < 10; x++) { System.out.print(a[x] + " "); } System.out.println(); sum++; } return; } for (int j = 1; j <= 9; j++) { // 明确所有路径 // 如果将要填入的数与前面不冲突，则填入 if (!same(a, i, j)) { a[i] = j; // 选择分支路径 j choose(i + 1); // 递归深度+1 //若没有找到出口，则将当前位置重置为0，回溯，还原现场 a[i] = 0; } } } }