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.

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`.

Idea:

Use DFS Template

Solution 1:

``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function(root) {
if (root === null) return;
let res = [];
let cur = [];
dfs(root, res, cur);
let sum = 0;
for (let num of res) {
sum += num;
}
return sum;
};

function dfs(root, res, cur) {
// exit recursion:
if (root === null) return;
// found leaf, save the number
if (root.left === null && root.right === null) {
cur.push(root.val);
res.push(parseInt(cur.join('')));
cur.pop();
return;
}

// possible solution
if (root !== null) {
cur.push(root.val);
dfs(root.left, res, cur);
dfs(root.right, res, cur);
cur.pop();
}
return;
}``````

Solution 2: (Version 2)

``````var sumNumbers = function(root) {
if (root === null) return;
let res = [0];
let cur = [0];
dfs(root, res, cur);
return res[0];
};

function dfs(root, res, cur) {
// exit recursion:
if (root === null) return;
// found leaf, save the number
if (root.left === null && root.right === null) {
cur[0] = cur[0] * 10 + root.val;
res[0] += cur[0];
cur[0] = (cur[0] - root.val) / 10;
return;
}

// possible solution
if (root !== null) {
cur[0] = cur[0] * 10 + root.val;
dfs(root.left, res, cur);
dfs(root.right, res, cur);
cur[0] = (cur[0] - root.val) / 10;
}
return;
}``````