129 Sum Root to Leaf Numbers

Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path1->2->3which represents the number123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path1->2represents the number12. The root-to-leaf path1->3represents the number13.

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

    return total_sum;
}