# 129 Sum Root to Leaf Numbers

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

**The Idea:** Using a single DFS traversal, we can capture the elements as we iterate to build up a new string. Once a leaf is reached, we can push the collected string to a vector. Once we both left and right children are explored, we popback once to obtain an earlier state in the recursion of the string

**Possible Improvements:** We can maintain accumulate the elements immediately rather than storing them into a vector.

```cpp
void dfs_root_sum(TreeNode *cur_node, string &cur_string, vector<int> &root_leaf_paths)
{
    if (cur_node) {
        cur_string += to_string(cur_node->value);

        // is leaf node
        if (!cur_node->left && !cur_node->right) {
            root_leaf_paths.push_back(stoi(cur_string));
        }

        dfs_root_sum(cur_node->left, cur_string, root_leaf_paths);
        dfs_root_sum(cur_node->right, cur_string, root_leaf_paths);
        cur_string.pop_back();
    }
}


int sumNumbers(TreeNode *root)
{
    vector<int> root_leaf_paths;
    string cur_string;

    dfs_root_sum(root, cur_string, root_leaf_paths);

    int total_sum = 0;
    for (int i : root_leaf_paths) {
        total_sum += i;
    }

    return total_sum;
}
```