做网站要学那些东西,想做网站,老区建设网站,下载app软件安装作者简介#xff1a;大家好#xff0c;我是未央#xff1b; 博客首页#xff1a;未央.303 系列专栏#xff1a;递归、搜索与回溯算法 每日一句#xff1a;人的一生#xff0c;可以有所作为的时机只有一次#xff0c;那就是现在#xff01;#xff01;#xff01;大家好我是未央 博客首页未央.303 系列专栏递归、搜索与回溯算法 每日一句人的一生可以有所作为的时机只有一次那就是现在 文章目录
前言
一、求根节点到叶节点数字之和
1.1 题目描述
1.2 题目解析
1.2.1 算法原理
1.2.2 代码编写
二、二叉树剪枝
2.1 题目描述
2.2 题目解析
2.2.1 算法原理
2.2.2 代码编写
总结 前言
今天是递归搜索剪枝的第五节内容
一、求根节点到叶节点数字之和
1.1 题目描述 描述 给你一个二叉树的根节点 root 树中每个节点都存放有一个 0 到 9 之间的数字。 举例说明从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点。 提示 树中节点的数目在范围 [1, 1000] 内。0 Node.val 9。树的深度不超过 10。 示例1 示例2 1.2 题目解析
1.2.1 算法原理 我们之前说要采用递归方法解决是从宏观的角度看待问题直接将问题扔给黑盒进行处理即可但是有些问题中黑盒执行的任务太多了不太好叙述清楚函数头和函数体都不好进行分析和编写 本题我们可以采用递归的方法解决 而要写好一个递归首先就要知道递归的三部曲 第一步 先找一下是否有和主问题相同的子问题----- 关系到函数头的设计 第二步 只需要关心某一个子问题是如何解决即可----- 关系到函数体的书写 第三步 最后再注意一下递归函数的出口即可 所以我们首先就要思考以上三个问题的解决 第一步函数头 我们题目要求将左右子树遍历的数相加返回给根节点 将左右子树遍历的数相加之后返回给根节点就成了和主问题相同的子问题 而函数头就和题目中给定的函数头不一样 所以我们要重写编写一个函数函数参数为根节点前驱的那个和 第二步函数体 我们要找到某一个子问题如何解决 子问题即 图示说明 要解决上述子问题 1先将选中根节点的前驱的和算出来给根节点 2要将前面遍历算出的125传给左子树 3要将前面遍历算出的125传给右子树 4左右子树都必须要返回最终的值相加后给根节点左1258右12594125931 第三步递归出口 递归出口即当遍历深搜到叶子结点的时候就没有左子树和右子树也就不用继续遍历了 注意这里的递归出口是在函数体1执行之后才进行判断执行的 因为你必须要把叶子结点的值连同前驱的和的值相加再向上进行返回的所以必须要先1将前驱的和算出来先给叶子节点才行 1.2.2 代码编写 代码解析 二、二叉树剪枝
2.1 题目描述 描述 给你二叉树的根结点 root 此外树的每个结点的值要么是 0 要么是 1 。 返回移除了所有不包含 1 的子树的原二叉树。 节点 node 的子树为 node 本身加上所有 node 的后代。 提示 树中节点的数目在范围 [1, 200] 内Node.val 为 0 或 1 示例1 示例2 示例3 2.2 题目解析
2.2.1 算法原理 本题我们主要需要掌握的是通过决策树能够抽象出递归的三部曲即函数体函数头递归出口只需要我们能够搞清楚递归的逻辑就能够找出递归的三部曲 思路分析 如果我们选择从上往下删除我们需要收集左右子树的信息这可能导致代码编写相对困难。然而通过观察我们可以发现如果我们先删除最底部的叶子节点然后再处理删除后的节点最终的结果 并不会受到影响。 因此我们可以采用序遍历的方式来解决这个问题。在后序遍历中我们先处理左子树然后处理右子树最后再处理当前节点。在处理当前节点时我们可以判断其是否为叶子节点且其值是否为 0 如果满足条件我们可以删除当前节点。 本题我们可以采用递归的方法解决 而要写好一个递归首先就要知道递归的三部曲 第一步 先找一下是否有和主问题相同的子问题----- 关系到函数头的设计 第二步 只需要关心某一个子问题是如何解决即可----- 关系到函数体的书写 第三步 最后再注意一下递归函数的出口即可 所以我们首先就要思考以上三个问题的解决 第一步函数头 我们题目要求返回移除了所有不包含 1 的子树的原二叉树。 而将返回移除了所有不包含 1 的子树就成了和主问题相同的子问题 而函数头就和题目中给定的函数头一样即返回当前需要处理的头节点 第二步函数体 我们要找到某一个子问题如何解决 子问题即返回移除了所有不包含 1 的子树 图示说明 要解决上述子问题后序遍历 1递归处理左子树 2递归处理右子树 3处理当前节点判断该节点是否为叶子节点即左右子节点均被删除当前节点成为叶子节点 并且节点的值为 0 a. 如果是就删除掉 b. 如果不是就不做任何处理。 第三步递归出口 即当传入节点为空时则直接返回空即可 注意 1在删除叶子节点时其父节点很可能会成为新的叶子节点。因此在处理完子节点后我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因后序遍历首先遍历到的⼀定 是叶子节点。 2通过使用后序遍历我们可以逐步删除叶子节点并且保证删除后的节点仍然满足删除操作的要求。这样我们可以较为方便地实现删除操作而不会影响最终的结果。 3若在处理结束后所有叶子节点的值均为 1则所有子树均包含 1此时可以返回。 2.2.2 代码编写 代码解析 总结
