《算法题讲解指南：递归，搜索与回溯算法--二叉树中的深搜》--6.计算布尔二叉树的值，7.求根节点到叶节点数字之和

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》

《算法题讲解指南》–优选算法

《算法题讲解指南》–递归、搜索与回溯算法

✨未择之路，不须回头 已择之路，纵是荆棘遍野，亦作花海遨游

目录

深度优先遍历介绍

6.计算布尔二叉树的值

题目链接：

题目描述：

题目示例：

解法(递归)：

算法思路：

C++算法代码：

7.求根节点到叶节点数字之和

题目链接：

题目描述：

题目示例：

解法(dfs-前序遍历)：

算法思路：

算法总结及流程解析：

结束语

深度优先遍历介绍

      深度优先遍历(DFS，全称为 Depth First Traversal)，是我们树或者图这样的数据结构中常用的一种遍历算法。这个算法会尽可能深的搜索树或者图的分支，直到一条路径上的所有节点都被遍历完毕，然后再回溯到上一层，继续找一条路遍历。       在二叉树中，常见的深度优先遍历为：前序遍历、中序遍历以及后序遍历。       因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。并且前中后序三种遍历的唯一区别就是访问根节点的时机不同，在做题的时候，选择一个适当的遍历顺序，对于算法的理解是非常有帮助的。

6.计算布尔二叉树的值

题目链接：

2331. 计算布尔二叉树的值 – 力扣（LeetCode）

题目描述：

题目示例：

解法(递归)：

算法思路：

      本题可以被解释为：       1.对于规模为 n 的问题，需要求得当前节点值。       2.节点值不为 0或1 时，规模为 n 的问题可以被拆分为规模为 n-1 的子问题：           a.所有子节点的值;           b.通过子节点的值运算出当前节点值。       3.当问题的规模变为 n=1 时，即叶子节点的值为 0或1，我们可以直接获取当前节点值为 0或1。

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:
bool evaluateTree(TreeNode* root)
{
//解法：递归(dfs)
//递归结束条件：当结点没有左右孩子时返回该结点值
if(root->left == nullptr && root->right == nullptr)
{
return root->val;
//因为到递归结束时也就是到叶子结点时，因为叶子结点只有0和1两个值
//并且这两个值就可以代表false和true，所以直接返回root->val即可
}
root->left->val = evaluateTree(root->left);
root->right->val = evaluateTree(root->right);
return root->val == 2 ? root->left->val || root->right->val : root->left->val && root->right->val;
}
};

7.求根节点到叶节点数字之和

题目链接：

129. 求根节点到叶节点数字之和 – 力扣（LeetCode）

题目描述：

题目示例：

解法(dfs-前序遍历)：

      前序遍历按照根节点、左子树、右子树的顺序遍历二叉树的所有节点，通常用于子节点的状态依赖于父节点状态的题目。

算法思路：

      在前序遍历的过程中，我们可以往左右子树传递信息，并且在回溯时得到左右子树的返回值。递归函数可以帮我们完成两件事：

      1.将父节点的数字与当前节点的信息整合到一起，计算出当前节点的数字，然后传递到下一层进行递归；       2.当遇到叶子节点的时候，就不再向下传递信息，而是将整合的结果向上一直回溯到根节点。

      在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。

/**
* 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)
{
if(root->left == nullptr && root->right == nullptr)
{
return root->val;
}

int leftsum = 0, rightsum = 0;
if(root->left)
{
TreeNode* left = root->left;
left->val = root->val * 10 + root->left->val;
leftsum = sumNumbers(left);
}
if(root->right)
{
TreeNode* right = root->right;
right->val = root->val * 10 + root->right->val;
rightsum = sumNumbers(right);
}
return leftsum + rightsum;
}
};

算法总结及流程解析：

结束语

      到此，6.计算布尔二叉树的值，7.求根节点到叶节点数字之和 这两道算法题就讲解完了。计算布尔二叉树的值 通过递归求解子节点值，再根据运算符计算当前节点值； 求根节点到叶节点数字之和 采用前序遍历方式，在递归过程中传递并累加节点数值。希望大家能有所收获！