【深搜算法】（第四篇）

求根节点到叶节点数字之和（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;}
}