LeetCode: 129. Sum Root to Leaf Numbers

The Problem

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

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.

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.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

int sumNumbers(TreeNode* root) {
    int total = 0;

    sumNumbersHelper(root, total, 0);

    return total;

}

void sumNumbersHelper(TreeNode* root, int &total, int current) {
    if (root == NULL) return;

    current = current * 10 + root->val;
    if(root->left == NULL && root->right == NULL)
    total += current;

    sumNumbersHelper(root->left, total, current);
    sumNumbersHelper(root->right, total, current);

}

Here's what each part does:

1. int sumNumbers(TreeNode* root) {: This is like the boss function. It sets up everything to start counting the numbers.
2. int total = 0;: Here, we create a total variable, which will store the sum of all the numbers we find.
3. sumNumbersHelper(root, total, 0);: We call a helper function to do most of the work. We give it the tree's root, the total variable, and a starting number of 0.
4. return total;: After the helper function does its job, we return the total sum.

Now, let's look at the helper function:

1. void sumNumbersHelper(TreeNode* root, int &total, int current) {: This is like the assistant who helps the boss. It does the real work.
2. if (root == NULL) return;: If there's no node here, we stop and go back to the boss function.
3. current = current * 10 + root->val;: We take the number we've been building (current), multiply it by 10 to shift its digits to the left, and then add the value of the current person (node).
4. if (root->left == NULL && root->right == NULL) total += current;: If we're at the end of a path (a leaf), we add the number we've built (current) to the total sum.
5. sumNumbersHelper(root->left, total, current);: We then check the left side of the tree and do the same process.
6. sumNumbersHelper(root->right, total, current);: After the left side is done, we check the right side and do the same thing.