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 % 1003.
Example :
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.
Return the sum = (12 + 13) % 1003 = 25 % 1003 = 25.
Method:
DFS
Solution:
Time: O(n) Space: O(n)
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { * val = x; * left=null; * right=null; * } * } */ public class Solution { public int sumNumbers(TreeNode A) { List<Integer> sums = new ArrayList<>(); getSums(sums, A, 0); int sum = 0; for (int i : sums) { sum += i; } return sum % 1003; }
private void getSums(List<Integer> sums, TreeNode A, int num) { if (A == null) return; if (A.left == null && A.right == null) { sums.add((num * 10) % 1003 + A.val % 1003); return; } if (A.left != null) { getSums(sums, A.left, (num * 10) % 1003 + A.val % 1003); } if (A.right != null) { getSums(sums, A.right, (num * 10) % 1003 + A.val % 1003); } } }