给你一个二叉树的根节点 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提示：
- 树中节点的数目在范围
[1, 1000]内 0 <= Node.val <= 9- 树的深度不超过
10
解题思路：深度优先搜索 + 前序遍历
因为我们得知道从根节点到每个叶子节点的路径代表的数字和，所以我们就得使用前序遍历来遍历整棵二叉树，在遍历过程中需要有一个变量 tmp 来记录当前走过的路径代表的数。
然后我们只需要判断当前节点是否为叶子节点，是的话直接将最后该叶子节点和 tmp 进行运算后返回给上一层即可；如果不是的话，说明此时还没到可以返回的时机，则递归到左右子树去处理，直到走到叶子节点然后遍历完整棵二叉树为止！
在遍历期间要注意的是我们可以不需要在递归函数开头给出递归函数的出口，因为题目节点个数是大于零的，所以保证一开始是不会访问空指针的，我们只需要在递归左右子树之前判断左右孩子节点是否存在即可，其它的没啥大问题！
/**
* 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 tmp)
{
// 进行先序遍历处理，只不过是专门对叶子节点处理
// 因为题目节点个数是大于零的，所以保证不会访问空指针
tmp = tmp*10 + root->val;
if(root->left == nullptr && root->right == nullptr)
return tmp;
// 如果不是叶子节点的话，则继续递归左右子树，并且将左右子树的结果累加到ret上进行返回
int ret = 0;
if(root->left) ret += dfs(root->left, tmp);
if(root->right) ret += dfs(root->right, tmp);
return ret;
}
}; 这里还有另一种写法，就是我们的递归函数可以不搞返回值，而是用一个变量 sum 来记录路径代表数的总和，要注意的是形参是一个地址或者引用，这样子才能保证全局累加的时候是对同一个 sum 进行累加！
/**
* 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) {
int sum = 0;
dfs(root, 0, sum);
return sum;
}
void dfs(TreeNode* root, int tmp, int& sum)
{
// 进行先序遍历处理，只不过是专门对叶子节点处理
sum += tmp*10 + root->val;
if(root->left == nullptr && root->right == nullptr)
return;
if(root->left) dfs(root->left, tmp*10 + root->val, sum);
if(root->right) dfs(root->right, tmp*10 + root->val, sum);
}
};