【深搜算法】（第四篇）

目录

求根节点到叶节点数字之和（medium）

题目解析

讲解算法原理

编写代码

⼆叉树剪枝（medium）

题目解析

讲解算法原理

编写代码

求根节点到叶节点数字之和（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个⼆叉树的根节点root，树中每个节点都存放有⼀个0到9之间的数字。每条从根节点到叶节点的路径都代表⼀个数字：
例如，从根节点到叶节点的路径1->2->3表⽰数字123。计算从根节点到叶节点⽣成的所有数字之和。
叶节点是指没有⼦节点的节点。

⽰例1：

输⼊：root=[1,2,3]输出：25
解释：
从根到叶⼦节点路径1->2代表数字12从根到叶⼦节点路径1->3代表数字13
因此，数字总和=12+13=25

⽰例2：

输⼊：root=[4,9,0,5,1]输出：1026
解释：
从根到叶⼦节点路径4->9->5代表数字495从根到叶⼦节点路径4->9->1代表数字491从根到叶⼦节点路径4->0代表数字40
因此，数字总和=495+491+40=1026

讲解算法原理

解法（dfs-前序遍历）：

前序遍历按照根节点、左⼦树、右⼦树的顺序遍历⼆叉树的所有节点，通常⽤于⼦节点的状态依赖于⽗节点状态的题⽬。

算法思路：
在前序遍历的过程中，我们可以往左右⼦树传递信息，并且在回溯时得到左右⼦树的返回值。递归函数可以帮我们完成两件事：
1. 将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递归；

2. 当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点。在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。
算法流程：

递归函数设计：intdfs(TreeNode*root,intnum)

1. 返回值：当前⼦树计算的结果（数字和）；
2. 参数num：递归过程中往下传递的信息（⽗节点的数字）；
3. 函数作⽤：整合⽗节点的信息与当前节点的信息计算当前节点数字，并向下传递，在回溯时返回当前⼦树（当前节点作为⼦树根节点）数字和。
递归函数流程：
1. 当遇到空节点的时候，说明这条路从根节点开始没有分⽀，返回0；
2. 结合⽗节点传下的信息以及当前节点的val，计算出当前节点数字sum；
3. 如果当前结点是叶⼦节点，直接返回整合后的结果sum；
4. 如果当前结点不是叶⼦节点，将sum传到左右⼦树中去，得到左右⼦树中节点路径的数字和，然后相加后返回结果。

编写代码

c++算法代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), 
right(right) {}
 * };
 */
class Solution
{
public:
 int sumNumbers(TreeNode* root) 
 {
 return dfs(root, 0);
 }
 int dfs(TreeNode* root, int presum)
 {
 presum = presum * 10 + root->val;
 if(root->left == nullptr && root->right == nullptr)
 return presum;
 int ret = 0;
 if(root->left) ret += dfs(root->left, presum);
 if(root->right) ret += dfs(root->right, presum);
 return ret;
 }
};

java算法代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution
{
 public int sumNumbers(TreeNode root) 
 {
 return dfs(root, 0);
 }
 public int dfs(TreeNode root, int preSum)
 {
 preSum = preSum * 10 + root.val;
 if(root.left == null && root.right == null)
 return preSum;
 
 int ret = 0;
 if(root.left != null) ret += dfs(root.left, preSum);
 if(root.right != null) ret += dfs(root.right, preSum);
 return ret;
 } 
}

⼆叉树剪枝（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼆叉树的根结点root，此外树的每个结点的值要么是0，要么是1。返回移除了所有不包含1的⼦树的原⼆叉树。
节点node的⼦树为node本⾝加上所有node的后代。
⽰例1：

输⼊：root=[1,null,0,0,1]
输出：[1,null,0,null,1]
解释：只有红⾊节点满⾜条件“所有不包含1的⼦树”。右图为返回的答案。

⽰例2：

输⼊：root=[1,0,1,0,0,0,1]输出：[1,null,1,null,1]

讲解算法原理

解法（dfs-后序遍历）：

后序遍历按照左⼦树、右⼦树、根节点的顺序遍历⼆叉树的所有节点，通常⽤于⽗节点的状态依赖于⼦节点状态的题⽬。

算法思路：
如果我们选择从上往下删除，我们需要收集左右⼦树的信息，这可能导致代码编写相对困难。然⽽，通过观察我们可以发现，如果我们先删除最底部的叶⼦节点，然后再处理删除后的节点，最终的结果并不会受到影响。
因此，我们可以采⽤后序遍历的⽅式来解决这个问题。在后序遍历中，我们先处理左⼦树，然后处理右⼦树，最后再处理当前节点。在处理当前节点时，我们可以判断其是否为叶⼦节点且其值是否为0，如果满⾜条件，我们可以删除当前节点。
• 需要注意的是，在删除叶⼦节点时，其⽗节点很可能会成为新的叶⼦节点。因此，在处理完⼦节点后，我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因（后序遍历⾸先遍历到的⼀定是叶⼦节点）。
• 通过使⽤后序遍历，我们可以逐步删除叶⼦节点，并且保证删除后的节点仍然满⾜删除操作的要
求。这样，我们可以较为⽅便地实现删除操作，⽽不会影响最终的结果。• 若在处理结束后所有叶⼦节点的值均为1，则所有⼦树均包含1，此时可以返回。
算法流程：

递归函数设计：voiddfs(TreeNode*&root)

1. 返回值：⽆；
2. 参数：当前需要处理的节点；

3. 函数作⽤：判断当前节点是否需要删除，若需要删除，则删除当前节点。
后序遍历的主要流程：
1. 递归出⼝：当传⼊节点为空时，不做任何处理；
2. 递归处理左⼦树；
3. 递归处理右⼦树；
4. 处理当前节点：判断该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶⼦节点），并且节点的值为0：
a. 如果是，就删除掉；
b. 如果不是，就不做任何处理。

编写代码

c++算法代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), 
right(right) {}
 * };
 */
class Solution
{
public:
 TreeNode* pruneTree(TreeNode* root) 
 {
 if(root == nullptr) return nullptr;
 root->left = pruneTree(root->left);
 root->right = pruneTree(root->right);
 if(root->left == nullptr && root->right == nullptr && root->val == 0)
 {
 delete root; // 防⽌内泄漏
 root = nullptr;
 }
 return root;
 }
};

java算法代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution
{
 public TreeNode pruneTree(TreeNode root) 
 {
 if(root == null) return null;
 root.left = pruneTree(root.left);
 root.right = pruneTree(root.right);
 if(root.left == null && root.right == null && root.val == 0)
 root = null;
 return root;
 }
}