0129.md

129. Sum Root to Leaf Numbers

Level:

Topic:

Question

You are given the root of a binary tree containing digits from 0 to 9 only.

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.

Intuition

Recursive:

• when it's the leaf node, it's the last digit
  • mulitply and return
• and traverse to the next digit

Code

Time: O(n)
Space: O(n)

Recursive

public int sumNumbers(TreeNode root) {
    return helper(root, 0);
}

private int helper(TreeNode root, int val) {
    if (root == null)
        return 0;

    val = val*10 + root.val;
    if (root.left == null && root.right == null)
        return val;

    return helper(root.left, val) + helper(root.right, val);
}