珠海建站模板源码,无需付费在线观看渠道,厦门建设网官方网站,廊坊短视频优化关卡名 认识回溯思想 我会了✔️ 内容 1.复习递归和N叉树#xff0c;理解相关代码是如何实现的 ✔️ 2.理解回溯到底怎么回事 ✔️ 3.掌握如何使用回溯来解决二叉树的路径问题 ✔️
回溯可以视为递归的拓展#xff0c;很多思想和解法都与递归密切相关#xff0c;在很多… 关卡名 认识回溯思想 我会了✔️ 内容 1.复习递归和N叉树理解相关代码是如何实现的 ✔️ 2.理解回溯到底怎么回事 ✔️ 3.掌握如何使用回溯来解决二叉树的路径问题 ✔️
回溯可以视为递归的拓展很多思想和解法都与递归密切相关在很多材料中都将回溯都与递归同时解释例如本章2.1的路径问题就可以使用递归和回溯两种方法来解决。因此学习回溯时我们对比递归来分析其特征会理解更深刻。 关于递归和回溯的区别我们设想一个场景某猛男想脱单现在有两种策略
1.递归策略先与意中人制造偶遇然后了解人家的情况然后约人家吃饭有好感之后尝试拉人家的手没有拒绝就表白。2.回溯策略先统计周围所有的单身女孩然后一个一个表白 被拒绝就说“我喝醉了”然后就当啥也没发生继续找下一个。
其实回溯本质就这么个过程请读者学习本章时认真揣摩这个过程。 回溯最大的好处是有非常明确的模板所有的回溯都是一个大框架因此透彻理解回溯的框架是解决一切回溯问题的基础。第一章我们只干一件事那就是分析这个框架。 回溯不是万能的而且能解决的问题也是非常明确的例如组合、分割、子集、排列棋盘等等不过这些问题具体处理时又有很多不同本章我们梳理了多个最为热门的问题来解释请同学们认真对待。 回溯可以理解为递归的拓展而代码结构又特别像深度遍历N叉树因此只要知道递归理解回溯并不难难在很多人不理解为什么在递归语句之后要有个“撤销”的操作。 我们会通过图示轻松给你解释该问题。这里先假设一个场景你谈了个新女朋友来你家之前你是否会将你前任的东西赶紧藏起来回溯也一样有些信息是前任的要先处理掉才能重新开始。 回溯最让人激动的是有非常清晰的解题模板如下所示大部分的回溯代码框架都是这个样子具体为什么这样子我们后面再解释。
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素画成树就是树节点孩子的大小){处理节点;backtracking();回溯撤销处理结果;}}
回溯是有明确的解题模板的本章我们只干一件事——分析回溯的模板。
1 从N叉树说起
在解释回溯之前 我们先看一下N叉树遍历的问题我们知道在二叉树中按照前序遍历的过程如下所示
void treeDFS(TreeNode root) {if (root null)return;System.out.println(root.val);treeDFS(root.left);treeDFS(root.right);
}class TreeNode{int val;TreeNode left;TreeNode right;
}
假如我现在是一个三叉、四叉甚至N叉树该怎么办呢很显然这时候就不能用left和right来表示分支了使用一个List比较好也就是这样子
class TreeNode{int val;ListTreeNode nodes;
}
遍历的代码
public static void treeDFS(TreeNode root) {//递归必须要有终止条件if (root null){return;}// 处理节点System.out.println(root.val);//通过循环分别遍历N个子树for (int i 1; i nodes.length; i) {treeDFS(第i个子节点);}
} 到这里你有没有发现和上面说的回溯的模板非常像了是的非常像既然很像那说明两者一定存在某种关系。其他暂时不管现在你只要先明白回溯的大框架就是遍历N叉树就行了。
2 为什么有的问题暴力搜索也不行
我们说回溯主要解决暴力枚举也解决不了的问题什么问题这么神奇暴力都搞不定 看个例子 LeetCode77 给定两个整数 n 和 k返回 1 ... n 中所有可能的 k 个数的组合。例如输入n4k2则输出 [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]] 首先明确这个题是什么意思如果n4k2那就是从4个数中选择2个问你最后能选出多少组数据。 这个是高中数学中的一个内容过程大致这样如果n4那就是所有的数字为{1,2,3,4}
1.先取一个1则有[1,2][1,3][1,4]三种可能。2.然后取一个2因为1已经取过了不再取则有[2,3][2,4]两种可能。3.再取一个3因为1和2都取过了不再取则有[3,4]一种可能。4.再取4因为123都已经取过了所以直接返回null。5.所以最终结果就是[1,2][1,3][1,4][2,3][2,4][3,4]。
这就是我们思考该问题的基本过程写成代码也很容易双层循环轻松搞定 int n 4;for (int i 1; i n; i) {for (int j i 1; j n; j) {System.out.println(i j);}}
假如n和k都变大比如n是200k是3呢也可以三层循环基本搞定
int n 200;for (int i 1; i n; i) {for (int j i 1; j n; j) {for (int u j 1; u n; n) {System.out.println(i j u);}} 如何这里的K是5呢甚至是50呢你需要套多少层循环甚至告诉你K就是一个未知的正整数k你怎么写循环呢这时候已经无能为例了所以暴力搜索就不行了。 这就是组合类型问题除此之外子集、排列、切割、棋盘等方面都有类似的问题因此我们要找更好的方式。
3 回溯递归局部枚举放下前任
我们继续研究LeetCode77题我们图示一下上面自己枚举所有答案的过程。 n4时我们可以选择的n有 {1,2,3,4}这四种情况所以我们从第一层到第二层的分支有四个分别表示可以取1234。而且这里 从左向右取数取过的数不在重复取。 第一次取1集合变为234 因为k为2我们只需要再取一个数就可以了分别取234得到集合[1,2] [1,3] [1,4]以此类推。 横向 每次从集合中选取元素可选择的范围会逐步收缩到了取4时就直接为空了。 继续观察树结构可以发现图中每次访问到一次叶子节点(图中红框标记处)我们就找到了一个结果。虽然最后一个是空但是不影响结果。这相当于只需要把从根节点开始每次选择的内容分支达到叶子节点时将其收集起来就是想要的结果。 如果感觉不明显我们再画一个n5k3的例子 从图中我们发现元素个数n相当于树的宽度横向而每个结果的元素个数k相当于树的深度纵向。所以我们说回溯算法就是一纵一横而已。再分析我们还发现几个规律 ① 我们每次选择都是从类似{1,2,3,4}{1,2,3,4,5}这样的序列中一个个选的这就是局部枚举而且越往后枚举范围越小。 ② 枚举时我们就是简单的暴力测试而已一个个验证能否满足要求从上图可以看到这就是N叉树遍历的过程因此两者代码也必然很像。 ③ 我们再看上图中红色大框起来的部分这个部分的执行过程与n4k2的处理过程完全一致很明显这是个可以递归的子结构。 这样我们就将回溯与N叉树的完美结合在一起了。 到此还有一个大问题没有解决回溯一般会有个手动撤销的操作为什么要这样呢继续观察纵横图 我们可以看到我们收集每个结果不是针对叶子结点的而是针对树枝的比如最上层我们首先选了1下层如果选2结果就是{1,2}如果下层选了3结果就是{1,3}依次类推。现在的问题是当我们得到第一个结果{1,2}之后怎么得到第二个结果{1,3}呢 继续观察纵横图可以看到我可以在得到{1,2}之后将2撤掉再继续取3这样就得到了{1,3}同理可以得到{1,4}之后当前层就没有了我们可以将1撤销继续从最上层取2继续进行。 这里对应的代码操作就是先将第一个结果放在临时列表path里得到第一个结果{1,2}之后就将path里的内容放进结果列表resultList中之后将path里的2撤销掉 继续寻找下一个结果{1.3},然后继续将path放入resultLit然后再撤销继续找。 现在明白为什么要手动撤销了吧这个过程我称之为放下前任继续前进后面所有的回溯问题都是这样的思路。 这几条就是回溯的基本规律明白之后一切都变得豁然开朗。如果还是不太明白我们下一小节用更完整的图示解释该过程。 到此我们就可以写出完整的回溯代码了:
public ListListInteger combine(int n, int k) {ListListInteger resultList new ArrayList();if(k0 || nk){return resultList;}// 用户返回结果DequeInteger path new ArrayList();dfs(n,k,1,path,resultList);return resultList;
}
public void dfs(int n,int k,int startIndex,Deque path,ListListInteger resultList){// 递归终止条件是path 的长度等于 kif(path.size()k){resultList.add(new ArrayList(path));return;}// 针对一个结点遍历可能的搜索起点其实就是枚举for(int istartIndex;in;i){// 向路径变量里添加一个数就是上图中的一个树枝的值path.addLast(i);// 搜索起点要加1是为了缩小范围下一轮递归做准备因为不允许出现重复的元素dfs(n,k,i1,path,resultList);// 递归之后需要做相同操作的逆向操作,具体后面继续解释path.removeLast();}
} 上面代码还有个问题要解释一下startIndex和i是怎么变化的为什么传给下一层时要加1。 我们可以看到在递归里有个循环
for (int i startIndex; i n; i) {dfs(n,k,i1,path,res);}
这里的循环有什么作用呢看一下图就知道了这里其实就是枚举第一次n4可以选择1 234四种情况所以就有四个分支for循环就会执行四次 而对于第二层第一个选择了1之后剩下的元素只有2 3 4了所以这时候for循环就执行3次后面的则只有2次和1次。
4 图解为什么有个撤销的操作
如果你已经明白上面为什么会有撤销过程这一小节就不必看了。如果还是不懂本节就用更详细的图示带你看一下。 回溯最难理解的部分是这个回溯过程而且这个过程即使调试也经常会晕 path.addLast(i); dfs(n, k, i 1, path, res); path.removeLast(); 为什么要remove呢看下图当第一层取1时最底层的边从左向右依次执行“取2”、“取3”和“取4”而取3的时候此时list里面存的是上一个结果1,2所以必须提前将2撤销这就path.removeLast();的作用。 用我们拆解递归的方法将递归拆分成函数调用输出第一条路径{1,2}的步骤如下如下 我们在递归章节说过递归是“不撞南墙不回头”回溯也一样接下来画代码的执行图详细看一下其过程图中的手绘的序号是执行过程: 然后呢{1,2}输出 之后会怎么执行呢回归之后假如我们将remove代码去掉也就是这样子 注意上面的4号位置结束之后当前递归就结束了然后返回到上一层继续执行for循环体也就是上面的5。进入5之后接着开始执行第6步path.addLast(i)了此时path的大小是3元素是{1,2,3}为什么会这样呢 因为path是一个全局的引用各个递归函数共用的所以当{1,2}处理完之后2污染了path变量。我们希望将1保留而将2干掉然后让3进来这样才能得到{1,3}所以这时候需要手动remove一下。 同样3处理完之后我们也不希望3污染接下来的{1,4}1全部走完之后也不希望1污染接下来的{2,3}等等这就是为什么回溯里会在递归之后有一个remove撤销操作。
5 回溯热身—再论二叉树的路径问题
5.1 输出二叉树的所有路径
LeetCode257给你一个二叉树的根节点root 按任意顺序 返回所有从根节点到叶子节点的路径。 叶子节点是指没有子节点的节点。 示例 输入root [1,2,3,null,5] 输出[1-2-5,1-3] 我们可以注意到有几个叶子节点就有几条路径那如何找叶子节点呢我们知道深度优先搜索就是从根节点开始一直找到叶子结点我们这里可以先判断当前节点是不是叶子结点再决定是不是向下走如果是叶子结点我们就增加一条路径。 我们现在从回溯的角度来分析得到第一条路径ABD之后怎么找到第二条路径ABE这里很明显就是先将D撤销然后再继续递归就可以了 class BinaryTreePaths {ListString ans new ArrayList();public ListString binaryTreePaths(TreeNode root) {dfs(root,new ArrayList());return ans;}private void dfs(TreeNode root, ListInteger temp){if(rootnull){return;}temp.add(root.val);//如果是叶子节点记录结果if(root.leftnullroot.rightnull){ans.add(getPathString(temp));}dfs(root.left,temp);dfs(root.right,temp);temp.remove(temp.size()-1);}//拼接结果private String getPathString(ListInteger temp){StringBuilder sb new StringBuilder();sb.append(temp.get(0));for(int i1;itemp.length();i){sb.append(-).append(temp.get(i));}return sb.toString();}
}
5.2 路径总和问题
同样的问题是LeetCode113题给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例1 输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22 输出[[5,4,11,2],[5,8,4,5]] 本题怎么做呢我们直接观察题目给的示意图即可要找的targetSum是22。我们发现根节点是5因此只要从左侧或者右侧找到targetSum是17的即可。继续看左子树我们发现值为4那只要从node(4)的左右子树中找targetSum是13即可依次类推当我们到达node(11)时我们需要再找和为2的子链路显然此时node(7)已经超了不是我们要的,此时就要将node(7)给移除掉继续访问node(2). 同样在根结点的右侧我们也要找总和为17的链路方式与上面的一致。完整代码就是
class PathSum {ListListInteger resnew ArrayList();public ListListInteger pathSum(TreeNode root, int targetSum) {LinkedListInteger pathnew LinkedList();dfs(root,targetSum,path);return res;}public void dfs(TreeNode root,int targetSum,LinkedListInteger path){if(rootnull){return;}//这个值有很关键的作用targetSum-root.val;path.add(root.val);if(targetSum0 root.leftnull root.rightnull){res.add(new LinkedList(path));}dfs(root.left,targetSum,path);dfs(root.right,targetSum,path);path.removeLast();}
}
