【递归、搜索与回溯算法】第五节.129. 求根节点到叶节点数字之和和814. 二叉树剪枝

作者简介：大家好，我是未央；

博客首页：未央.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；右12594+125931）

---

第三步：递归出口

递归出口即：当遍历深搜到叶子结点的时候，就没有左子树和右子树，也就不用继续遍历了

注意：这里的递归出口是在函数体（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 代码编写

代码解析：

总结