Algorithm
Problem Name: 129. Sum Root to Leaf Numbers
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 -> 3represents the number123.
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 1:
Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path1->2represents the number12. The root-to-leaf path1->3represents the number13. Therefore, sum = 12 + 13 =25.
Example 2:
Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path4->9->5represents the number 495. The root-to-leaf path4->9->1represents the number 491. The root-to-leaf path4->0represents the number 40. Therefore, sum = 495 + 491 + 40 =1026.
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.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void sumNumbersHelper(struct TreeNode* root, int* sum, int num) {
if (root == NULL) return;
num = num * 10 + root->val;
if (root->left == NULL && root->right == NULL) {
*sum += num;
return;
}
sumNumbersHelper(root->left, sum, num);
sumNumbersHelper(root->right, sum, num);
}
int sumNumbers(struct TreeNode* root) {
if (root == NULL) return 0;
int sum = 0, num = 0;
sumNumbersHelper(root, &sum, num);
return sum;
}
int main() {
struct TreeNode* root = (struct TreeNode *)calloc(3, sizeof(struct TreeNode));
root->val = 1;
root->left = root + 1;
root->left->val = 2;
root->right = root + 2;
root->right->val = 3;
/* should be 25 */
printf("%d\n", sumNumbers(root));
return 0;
}
Input
root = [1,2,3]
Output
25
#2 Code Example with C++ Programming
Code -
C++ Programming
// DFS
class Solution {
public:
int sumNumbers(TreeNode* root) {
if(!root) return 0;
int res = 0;
dfs(root, res, 0);
return res;
}
void dfs(TreeNode* root, int& res, int num){
num = num * 10 + root->val;
if(root->left) dfs(root->left, res, num);
if(root->right) dfs(root->right, res, num);
if(!root->left && !root->right) res += num;
}
};
// BFS
class Solution {
public:
int sumNumbers(TreeNode* root) {
if(!root) return 0;
int res = 0;
queue<pair < TreeNode*, int>>q;
q.push({root, 0});
while(!q.empty()){
auto p = q.front();
q.pop(>;
int num = p.second * 10 + p.first->val;
if(p.first->left) q.push({p.first->left, num});
if(p.first->right) q.push({p.first->right, num});
if(!p.first->left && !p.first->right) res += num;
}
return res;
}
};
Input
root = [1,2,3]
Output
25
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int sumNumbers(TreeNode root) {
int[] sum = {0};
helper(root, 0, sum);
return sum[0];
}
private void helper(TreeNode root, int currValue, int[] sum) {
if (root == null) {
return;
}
currValue = currValue * 10 + root.val;
if (root.left == null && root.right == null) {
sum[0] += currValue;
return;
}
helper(root.left, currValue, sum);
helper(root.right, currValue, sum);
}
}
Input
root = [1,2,3]
Output
25
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const sumNumbers = function(root) {
const sum = []
rec(root, '', sum)
return sum.reduce((ac, el) => ac + el, 0)
};
function rec(node, str, arr) {
if (node == null) {
arr.push(+str)
return
}
if (node.left !== null) {
rec(node.left, str + node.val, arr)
}
if (node.right !== null) {
rec(node.right, str + node.val, arr)
}
if (node.left === null && node.right === null) {
arr.push(+(str + node.val) )
}
}
Input
root = [1,2,3]
Output
25
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def traverse(node, q):
if not node: return
traverse(node.left, q + [str(node.val)])
traverse(node.right, q + [str(node.val)])
if not node.left and not node.right: res[0] += int("".join(q + [str(node.val)]))
res = [0]
traverse(root, [])
return res[0]
Input
root = [1,2,3]
Output
25
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0129_SumRootToLeafNumbers
{
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public int SumNumbers(TreeNode root)
{
return SumNumbers(root, 0);
}
private int SumNumbers(TreeNode node, int number)
{
if (node == null) return 0;
var result = number * 10 + node.val;
if (node.left == null && node.right == null) return result;
return SumNumbers(node.left, result) + SumNumbers(node.right, result);
}
}
}
Input
root = [1,2,3]
Output
25