透析回溯的模板

2023-12-13 23:18:26

关卡名

认识回溯思想

我会了??

内容

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;
   List<TreeNode> 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 个数的组合。例如,输入n=4,k=2,则输出:
[[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

?首先明确这个题是什么意思,如果n=4,k=2,那就是从4个数中选择2个,问你最后能选出多少组数据。
这个是高中数学中的一个内容,过程大致这样:如果n=4,那就是所有的数字为{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,因为1,2,3都已经取过了,所以直接返回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是200,k是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题,我们图示一下上面自己枚举所有答案的过程。
n=4时,我们可以选择的n有 {1,2,3,4}这四种情况,所以我们从第一层到第二层的分支有四个,分别表示可以取1,2,3,4。而且这里 从左向右取数,取过的数,不在重复取。 第一次取1,集合变为2,3,4 ,因为k为2,我们只需要再取一个数就可以了,分别取2,3,4,得到集合[1,2] [1,3] [1,4],以此类推。
横向:

每次从集合中选取元素,可选择的范围会逐步收缩,到了取4时就直接为空了。
继续观察树结构,可以发现,图中每次访问到一次叶子节点(图中红框标记处),我们就找到了一个结果。虽然最后一个是空,但是不影响结果。这相当于只需要把从根节点开始每次选择的内容(分支)达到叶子节点时,将其收集起来就是想要的结果。
如果感觉不明显,我们再画一个n=5,k=3的例子:

从图中我们发现元素个数n相当于树的宽度(横向),而每个结果的元素个数k相当于树的深度(纵向)。所以我们说回溯算法就是一纵一横而已。再分析,我们还发现几个规律:
① 我们每次选择都是从类似{1,2,3,4},{1,2,3,4,5}这样的序列中一个个选的,这就是局部枚举,而且越往后枚举范围越小。
② 枚举时,我们就是简单的暴力测试而已,一个个验证,能否满足要求,从上图可以看到,这就是N叉树遍历的过程,因此两者代码也必然很像。
③ 我们再看上图中红色大框起来的部分,这个部分的执行过程与n=4,k=2的处理过程完全一致,很明显这是个可以递归的子结构。
这样我们就将回溯与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 List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> resultList = new ArrayList<>();
    if(k<=0 || n<k){
        return resultList;
    }
    // 用户返回结果
    Deque<Integer> path = new ArrayList<>();
    dfs(n,k,1,path,resultList);
    return resultList;
}
public void dfs(int n,int k,int startIndex,Deque path,List<List<Integer>> resultList){
    // 递归终止条件是:path 的长度等于 k
    if(path.size()==k){
        resultList.add(new ArrayList<>(path));
        return;
    }
    // 针对一个结点,遍历可能的搜索起点,其实就是枚举
    for(int i=startIndex;i<=n;i++){
        // 向路径变量里添加一个数,就是上图中的一个树枝的值
        path.addLast(i);
        // 搜索起点要加1是为了缩小范围,下一轮递归做准备,因为不允许出现重复的元素
        dfs(n,k,i+1,path,resultList);
        // 递归之后需要做相同操作的逆向操作,具体后面继续解释
        path.removeLast();
    }
}

?上面代码还有个问题要解释一下:startIndex和i是怎么变化的,为什么传给下一层时要加1。
我们可以看到在递归里有个循环

for (int i = startIndex; i <= n; i++) {
    dfs(n,k,i+1,path,res);
 }

这里的循环有什么作用呢?看一下图就知道了,这里其实就是枚举,第一次n=4,可以选择1 ,2,3,4四种情况,所以就有四个分支,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 {
    List<String> ans = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root,new ArrayList<>());
        return ans;
    }

    private void dfs(TreeNode root, List<Integer> temp){
        if(root==null){
            return;
        }
        temp.add(root.val);
        //如果是叶子节点记录结果
        if(root.left==null&&root.right==null){
            ans.add(getPathString(temp));
        }
        dfs(root.left,temp);
        dfs(root.right,temp);
        temp.remove(temp.size()-1);
    }
    //拼接结果
    private String getPathString(List<Integer> temp){
        StringBuilder sb = new StringBuilder();
        sb.append(temp.get(0));
        for(int i=1;i<temp.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 {
    List<List<Integer>> res=new ArrayList<>();
    
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        LinkedList<Integer> path=new LinkedList<>();
        dfs(root,targetSum,path);
        return res;
    }
    
    public void dfs(TreeNode root,int targetSum,LinkedList<Integer> path){
        if(root==null){
            return;
        }
        //这个值有很关键的作用
        targetSum-=root.val;
        path.add(root.val);
        if(targetSum==0 && root.left==null && root.right==null){
            res.add(new LinkedList(path));
        }
        dfs(root.left,targetSum,path);
        dfs(root.right,targetSum,path);
        path.removeLast();
    }
}

文章来源:https://blog.csdn.net/m0_53401014/article/details/134960332
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。