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.

**Note:** A leaf is a node with no children.

**Example:**

Input:[1,2,3] 1 / \ 2 3Output:25Explanation: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:[4,9,0,5,1] 4 / \ 9 0 / \ 5 1Output:1026Explanation: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`

.

**Solution Using DFS:**

We will DFS(Depth First Search) to find the numbers and add them to the sum, the time complexity would be O(N).

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

In this video explanation we will solve Leetcode Sum Root to Leaf Numbers Java Solution