【递归搜索回溯专栏】专题二：二叉树中的深搜----求根节点到叶节点数字之和

题目来源

本题来源为：

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;
    }
};