> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0129-sum-root-to-leaf-numbers.md).

# 0129. Sum Root to Leaf Numbers

<https://leetcode.com/problems/sum-root-to-leaf-numbers>

## Description

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

![](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.
```

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

## ac1: Backtracking

use StringBuilder, slower

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int sum;
    public int sumNumbers(TreeNode root) {
        sum = 0;
        StringBuilder sb = new StringBuilder();
        backtrack(root, sb);
        return sum;
    }
    private void backtrack(TreeNode root, StringBuilder sb) {
        // exit
        if (root == null) return;
        // leaf
        sb.append(root.val);
        if (root.left == null && root.right == null) {
            sum += Integer.parseInt(sb.toString());
        }
        backtrack(root.left, sb);
        backtrack(root.right, sb);

        sb.setLength(sb.length() - 1);
    }
}
// DFS, backtracking
```

## ac2: devide & conquer

direct number calculation, so beautiful...

```java
class Solution {
    public int sumNumbers(TreeNode root) {
        return sum(root, 0);
    }
    private int sum(TreeNode root, int sum) {
        // exit
        if (root == null) return 0;
        // leaf
        if (root.left == null && root.right == null) {
            return sum*10 + root.val;
        }

        // devide & conquer
        return sum(root.left, sum*10 + root.val) + sum(root.right, sum*10 + root.val);
    }
}
```