本专栏内容为:递归,搜索与回溯算法专栏。 通过本专栏的深入学习,你可以了解并掌握算法。
💓博主csdn个人主页:小小unicorn
⏩专栏分类:递归搜索回溯专栏
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识
专题一
- 题目来源
- 题目描述
- 算法原理
- 函数头
- 函数体
- 返回值
- 代码实现
题目来源
本题来源为:
Leetcode 129. 求根节点到叶节点数字之和
题目描述
给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:
例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
算法原理
还是从例子下手,例如下面这个就是要将1247,1258,12594,125931,1367加起来的值就是我们需要的结果。
递归我们看一层,比如5这个节点,5这个节点我们需要干什么事情,他要拿到1258,12594,125931这三个的值然后返回给根节点。先看1258这个数,要想获得1258这个数,我们是不是首先要拿到12,因此要先把12拿过来。
那么所以:
第一步:当到5节点这一层要先算出125.
第二步:将125传给左边
第三步:将125传给右边
第四步:把两个返回值相加返回到上一层的节点。
那么其他层跟5节点是一样的,都需要这四步。
函数头
因为要记录上一层的值,因此要在传根的基础上加一个参数。
函数体
跟5节点分析一样,分成1 2 3 4步
返回值
当遇到为叶子节点时就返回。
注意递归出口是在第一步后结束的。
代码实现
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;
}
};