Skip to content

129 Sum Root to Leaf Numbers

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:

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:

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.

Solution: Recursion

Time complexity: O(n) Space complexity: O(h)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return sum(root, "");
    }
    private int sum(TreeNode root, String curr){
        if (root.left == null && root.right == null) {
            return Integer.parseInt(curr + root.val);
        }
        int sums = 0;
        if (root.left != null) {
            sums += sum(root.left, curr + root.val);
        }
        if (root.right != null) {
            sums += sum(root.right, curr + root.val);
        }
        return sums;
    }
}
class Solution {
public:
  int sumNumbers(TreeNode* root) {
    int ans = 0;
    function<void(TreeNode*, int)> traverse = [&](TreeNode* t, int num) {
      if (!t) return;
      num = num * 10 + t->val;
      if (t->left || t->right) {
        traverse(t->left, num);
        traverse(t->right, num);
      } else {
        ans += num;
      }
    };
    traverse(root, 0);
    return ans;
  }
};
public class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> data = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i ++) {
            data.add(nums[i]);
        }
        int max = 0;
        for (int i = 0; i < nums.length; i ++) {
            if (data.contains(nums[i])) {
                int count = 1;
                int tmp = nums[i] - 1;
                while (data.contains(tmp)){
                    data.remove(tmp);
                    tmp --;
                    count ++;
                }
                tmp = nums[i] + 1;
                while (data.contains(tmp)) {
                    data.remove(tmp);
                    tmp ++;
                    count ++;
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }
}
public class Solution {
    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> left = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> right = new HashMap<Integer, Integer>();
        HashSet<Integer> visited = new HashSet<Integer>();
        int max = 0;
        for (int i = 0; i < nums.length; i ++) {
            if (visited.contains(nums[i])) {
                continue;
            }
            if (!right.containsKey(nums[i] - 1) && !left.containsKey(nums[i] + 1)) {
                left.put(nums[i], nums[i]);
                right.put(nums[i], nums[i]);
                max = Math.max(max, 1);
                visited.add(nums[i]);
                continue;
            }
            if (right.containsKey(nums[i] - 1) && left.containsKey(nums[i] + 1)) {
                int a = right.get(nums[i] - 1);
                int b = left.get(nums[i] + 1);
                right.remove(nums[i] - 1);
                left.remove(nums[i] + 1);
                left.put(a, b);
                right.put(b, a);
                max = Math.max(max, b - a + 1);
                visited.add(nums[i]);
                continue;
            }
            if (right.containsKey(nums[i] - 1)) {
                int a = right.get(nums[i] - 1);
                int b = nums[i] - 1;
                right.remove(b);
                left.put(a, nums[i]);
                right.put(nums[i], a);
                max = Math.max(max, b - a + 2);
            }
            if (left.containsKey(nums[i] + 1)) {
                int a = nums[i] + 1;
                int b = left.get(nums[i] + 1);
                left.remove(a);
                left.put(nums[i], b);
                right.put(b, nums[i]);
                max = Math.max(max, b - a + 2);
            }
            visited.add(nums[i]);
        }
        return max;
    }
}