【Leetcode每日一题】递归 - 求根节点到叶节点数字之和（难度⭐⭐）（47）

1. 题目解析

题目链接：129. 求根节点到叶节点数字之和

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

递归函数设计：
我们设计了一个递归函数 int dfs(TreeNode* root, int num)，其中 root 表示当前遍历到的节点，num 是从父节点传递下来的数字信息。
递归函数的作用：
这个函数的主要作用是整合父节点的信息与当前节点的信息，计算出当前节点的数字，并将这个数字继续向下传递。同时，在回溯的过程中，它会返回当前子树（以当前节点为根节点）的数字和。
递归函数的流程：
- 空节点处理：如果当前节点是空节点，说明这条路径上没有节点，直接返回0。
- 计算当前节点数字：结合父节点传递下来的信息 num 和当前节点的值 root->val，计算出当前节点的数字 sum。
- 叶子节点处理：如果当前节点是叶子节点（没有左右子节点），那么直接返回计算后的数字 sum。
- 非叶子节点处理：如果当前节点不是叶子节点，那么将计算后的数字 sum 分别传递给左右子树，得到左右子树中节点路径的数字和，然后将这两个和相加，返回最终结果。

3.代码编写

/**
 * 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 sum(root, 0);
    }
    int sum(TreeNode* root, int num)
    {
        if(root->left == nullptr && root->right == nullptr) return num * 10 + root->val;
        int ret = 0;
        if(root->left) ret += sum(root->left, num * 10 + root->val);
        if(root->right) ret += sum(root->right, num * 10 + root->val);
        return ret;
    }
};