129 Sum Root to Leaf Numbers
Given a binary tree containing digits from
0-9only, each root-to-leaf path could represent a number.An example is the root-to-leaf path
1->2->3which represents the number123.Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path
1->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;
}
Last modified 3yr ago