# 129. Sum Root to Leaf Numbers

### Leetcode

<https://leetcode.com/problems/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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/19/num1tree.jpg)

```
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:**

![](https://assets.leetcode.com/uploads/2021/02/19/num2tree.jpg)

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

Recursion

```
var sumNumbers = function(root) {
    if(root === null) return 0;
    
    const res = []
    
    const helper = (node, number) => {
        const val = node.val;
        const nextNumber = (number + val.toString()).toString();
        
        if (!node.left && !node.right) {
            res.push(nextNumber);
        }
        if (node.left) {
            helper(node.left, nextNumber);
        }
        if (node.right) {
            helper(node.right, nextNumber);
        }
    }
    
    helper(root, '0');
    const sum = res.reduce((accu, curr) => {
        return accu + +curr;
    }, 0)
    return sum;
};
```

Runtime: 70 ms, faster than 75.20% of JavaScript online submissions for Sum Root to Leaf Numbers.

Memory Usage: 42 MB, less than 84.83% of JavaScript online submissions for Sum Root to Leaf Numbers.

* **方法二**

Iteration

```
var sumNumbers = function(root) {
    if (!root) return 0;
    
    const res = [];
    const queue = [{
        node: root,
        val: ''
    }];
    while (queue.length) {
        const curr = queue.shift();
        const node = curr.node;
        const nodeVal = node.val;
        const nextVal = (curr.val + nodeVal.toString()).toString();
        
        if (!node.left && !node.right) {
            res.push(+nextVal);
        }
        if (node.left) {
            queue.push({
                node: node.left,
                val: nextVal
            })
        }
        if (node.right) {
            queue.push({
                node: node.right,
                val: nextVal
            })
        }
    }
    
    const sum = res.reduce((accu, curr) => {
        return accu + curr;
    }, 0)
    return sum;
};
```

Runtime: 64 ms, faster than 90.68% of JavaScript online submissions for Sum Root to Leaf Numbers.

Memory Usage: 42.6 MB, less than 39.49% of JavaScript online submissions for Sum Root to Leaf Numbers.
