Leetcode 129. Sum Root to Leaf Numbers

Problem Explanation

The problem asks to find the sum of all root-to-leaf values. Each root-to-leaf path could represent a number where each node represents a digit of the number.

To understand the task, let's consider an example:

11

/
2 3

Here, we have two root-to-leaf paths: 1->2 and 1->3, which represent the numbers 12 and 13 respectively. Hence, the sum of the root-to-leaf paths would be 12 + 13 = 25.

Approach

To solve this problem, we can perform a Depth-First Search (DFS) on the given binary tree. Our approach is to use postorder traversal.

Here are the main parts of our approach:

• If the node is null, return, as this indicates that we've reached a leaf node.

• If the node is a leaf (i.e., it has no children), add the root-to-leaf number to the total sum. To calculate the root-to-leaf number, multiply the current number by 10 and add the value of the current node.

• If the node is not a leaf, continue the traversal on the left and the right subtree. To compute the current number, again multiply the current number by 10 and add the current node value.

For example, consider this tree:

14

/
9 0  /
5 1

The root-to-leaf paths are:

• 4->9->5 represents the number 495
• 4->9->1 represents the number 491
• 4->0 represents the number 40

Therefore, the sum of these numbers will be 495 + 491 + 40 = 1026.

Python Solution

1
2python
3class Solution:
4    def sumNumbers(self, root):
5        return self.dfs(root, 0)
6
7    def dfs(self, root, val):
8        if root is None:
9            return 0
10        val = val * 10 + root.val
11        if root.left is None and root.right is None:
12            return val
13        return self.dfs(root.left, val) + self.dfs(root.right, val)

Java Solution

1
2java
3class Solution {
4    public int sumNumbers(TreeNode root) {
5        return dfs(root, 0);
6    }
7
8    private int dfs(TreeNode root, int val) {
9        if(root == null)
10            return 0;
11        val = val * 10 + root.val;
12        if(root.left == null && root.right == null)
13            return val;
14        return dfs(root.left, val) + dfs(root.right, val);
15    }
16}

Javascript Solution

1
2javascript
3var sumNumbers = function(root, sum = 0) {
4    if(!root) return 0;
5    if(!root.left && !root.right) return sum*10+root.val;
6    return sumNumbers(root.left,sum*10+root.val) + sumNumbers(root.right,sum*10+root.val);
7};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int sumNumbers(TreeNode* root) {
6        return dfs(root, 0);   
7    }
8
9private:
10    int dfs(TreeNode* root, int sum) {
11        if (!root) return 0;
12        if (!root -> left && !root -> right) return sum*10 + root -> val;
13        return dfs(root -> left, sum*10 + root->val) + dfs(root -> right, sum*10 + root -> val);
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    public int SumNumbers(TreeNode root) {
5        return Dfs(root, 0);
6    }
7    
8    private int Dfs(TreeNode root, int sum) {
9        if (root == null) return 0;
10        sum = sum * 10 + root.val;
11        if (root.left == null && root.right == null) return sum;
12        return Dfs(root.left, sum) + Dfs(root.right, sum);
13    }
14}

To summarize, the problem of finding the sum of all root-to-leaf numbers in a binary tree can be solved through depth-first search and calculating the root-to-leaf number by multiplying the current number by 10 and adding the current node value. This approach is implemented in Python, Java, JavaScript, C++ and C#, with all solutions sharing a common algorithm but differing slightly due to the syntax and features of each programming language.

The solution involves recursion and careful control to ensure that each path is traversed from root to leaf, and the sum of each path is calculated accordingly. The base case for the recursion is when the node is null, indicating that a leaf node has been reached. If the node has no children, its value is added to the sum. If the node is not a leaf, the search continues on the left and right subtrees.

This problem demonstrates the importance of understanding how to traverse a tree using different types of depth-first search, and how to manipulate data correctly in a recursive function. Despite being a simple problem, it requires careful consideration and strong problem-solving skills.