# [LeetCode 129] Sum Root to Leaf Numbers

### Question

Given a binary tree containing digits from `0-9` only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path `1->2->3` which represents the number `123`.

Find the total sum of all root-to-leaf numbers.

For example,

```    1
/ \
2   3
```

The root-to-leaf path `1->2` represents the number `12`.
The root-to-leaf path `1->3` represents the number `13`.

Return the sum = 12 + 13 = `25`.

### Stats

 Frequency 4 Difficulty 2 Adjusted Difficulty 2 Time to use 10 minutes

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This is DFS standard question.

### Solution

I posted 2 pieces of my code, and 1 best code (from this blog).

### Code

First, my solution using List.

``````int sum = 0;

public int sumNumbers(TreeNode root) {
return sum;
}

private void dfs(TreeNode node, LinkedList<Integer> list) {
if (node == null) return;
if (node.left == null && node.right == null) {
int num = 0;
for (int i = 0; i < list.size(); i ++)
num = num * 10 + list.get(i);
sum += num * 10 + node.val;
return;
}
// if node is not null, not a leaf
dfs(node.left, list);
dfs(node.right, list);
list.remove(list.size() - 1);
}
``````

Second, previous code refactored, without using list, because it’s not necessary to know the previous path.

``````int sum = 0;
public int sumNumbers(TreeNode root) {
dfs(root, 0);
return sum;
}

private void dfs(TreeNode node, int preVal) {
if (node == null) return;
int curVal = preVal * 10 + node.val;
if (node.left == null && node.right == null) {
int num = 0;
sum += curVal;
return;
}
// if node is not null, not a leaf
dfs(node.left, curVal);
dfs(node.right, curVal);
}
``````

Third, best solution

``````public int sumNumbers(TreeNode root) {
return dfs(root,0);
}

int dfs(TreeNode root, int sum){
if(root==null) return 0;
sum=sum*10+root.val;
if(root.left==null && root.right==null) return sum;
return dfs(root.left,sum) + dfs(root.right,sum);
}
``````