[LeetCode] 129. Sum Root to Leaf Numbers

Posted on | In

Problem

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

An example is the root-to-leaf path 1->2->3 which represents the number 123.

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

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9
Input: [1,2,3]
    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.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Explanation

  1. We can use recursion method to solve. Whenever we encounted a root value, we will multiple the previous sum by 10 then add the current root value to become a new sum.
  2. We can think of the left node as a root, the right node as a root, then solve them recursivly and pass the new sum as left child and right child’s previous sum to the helper method to get their sums and add them both to become the root’s sum.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int helper(TreeNode root, int sum) {
        if (root == null) return 0;
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) return sum;
        return helper(root.left, sum) + helper(root.right, sum);
    }
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }
}