# 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.
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;
}