## Algorithm

Problem Name: 129. Sum Root to Leaf Numbers

You are given the `root` of a binary tree containing digits from `0` to `9` only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path `1 -> 2 -> 3` represents the number `123`.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

```Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path `1->2` represents the number `12`. The root-to-leaf path `1->3` represents the number `13`. Therefore, sum = 12 + 13 = `25`.```

Example 2:

```Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path `4->9->5` represents the number 495. The root-to-leaf path `4->9->1` represents the number 491. The root-to-leaf path `4->0` represents the number 40. Therefore, sum = 495 + 491 + 40 = `1026`.```

Constraints:

• The number of nodes in the tree is in the range `[1, 1000]`.
• `0 <= Node.val <= 9`
• The depth of the tree will not exceed `10`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};

void sumNumbersHelper(struct TreeNode* root, int* sum, int num) {
if (root == NULL) return;

num = num * 10 + root->val;
if (root->left == NULL && root->right == NULL) {
*sum += num;
return;
}

sumNumbersHelper(root->left, sum, num);
sumNumbersHelper(root->right, sum, num);
}

int sumNumbers(struct TreeNode* root) {
if (root == NULL) return 0;

int sum = 0, num = 0;
sumNumbersHelper(root, &sum, num);

return sum;
}

int main() {
struct TreeNode* root = (struct TreeNode *)calloc(3, sizeof(struct TreeNode));
root->val = 1;
root->left = root + 1;
root->left->val = 2;
root->right = root + 2;
root->right->val = 3;

/* should be 25 */
printf("%d\n", sumNumbers(root));

return 0;
}
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
25

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
// DFS
class Solution {
public:
int sumNumbers(TreeNode* root) {
if(!root) return 0;
int res = 0;
dfs(root, res, 0);
return res;
}

void dfs(TreeNode* root, int& res, int num){
num = num * 10 + root->val;
if(root->left) dfs(root->left, res, num);
if(root->right) dfs(root->right, res, num);
if(!root->left && !root->right) res += num;
}
};

// BFS
class Solution {
public:
int sumNumbers(TreeNode* root) {
if(!root) return 0;
int res = 0;
queue<pair < TreeNode*, int>>q;
q.push({root, 0});
while(!q.empty()){
auto p = q.front();
q.pop(>;
int num = p.second * 10 + p.first->val;
if(p.first->left) q.push({p.first->left, num});
if(p.first->right) q.push({p.first->right, num});
if(!p.first->left && !p.first->right) res += num;
}
return res;
}
};
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
25

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int sumNumbers(TreeNode root) {
int[] sum = {0};
helper(root, 0, sum);
return sum[0];
}

private void helper(TreeNode root, int currValue, int[] sum) {
if (root == null) {
return;
}
currValue = currValue * 10 + root.val;
if (root.left == null && root.right == null) {
sum[0] += currValue;
return;
}
helper(root.left, currValue, sum);
helper(root.right, currValue, sum);
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
25

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const sumNumbers = function(root) {
const sum = []
rec(root, '', sum)
return sum.reduce((ac, el) => ac + el, 0)
};

function rec(node, str, arr) {
if (node == null) {
arr.push(+str)
return
}
if (node.left !== null) {
rec(node.left, str + node.val, arr)
}
if (node.right !== null) {
rec(node.right, str + node.val, arr)
}
if (node.left === null && node.right === null) {
arr.push(+(str + node.val) )
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
25

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def traverse(node, q):
if not node: return
traverse(node.left, q + [str(node.val)])
traverse(node.right, q + [str(node.val)])
if not node.left and not node.right: res[0] += int("".join(q + [str(node.val)]))
res = [0]
traverse(root, [])
return res[0]
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
25

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0129_SumRootToLeafNumbers
{
/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public int SumNumbers(TreeNode root)
{
return SumNumbers(root, 0);
}

private int SumNumbers(TreeNode node, int number)
{
if (node == null) return 0;

var result = number * 10 + node.val;
if (node.left == null && node.right == null) return result;
return SumNumbers(node.left, result) + SumNumbers(node.right, result);
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
25