Dynamic Programming - Sum Root to Leaf Numbers

The hard part of this problem, is that people at least me always try to back track all nodes on the paths… but never move forward… (too lazy guys)

The idea is to analyze the eventual values on each leaves… what are values after accumulation from each path (each leaf is a separate path)… then dfs will help to do it with passing a result list and pre values by reference…

Be aware of that final result may be bigger than integer maximum… that case we need a long…

/**
 * Definition for binary tree
 * 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;
        }
        List<Integer> sums = new ArrayList<Integer>();
        findAllSums(root, 0, sums);
        long result = 0;
        for(int i = 0; i < sums.size(); i++){
            result += sums.get(i);
        }
        if(result > Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }
        return (int) result;
    }
   
    private void findAllSums(TreeNode node, int preDigit, List<Integer> sums){
        if(node.left == null && node.right == null){
            sums.add(preDigit * 10 + node.val);
            return;
        }
        if(node.left != null){
            findAllSums(node.left, preDigit*10 + node.val, sums);
        }
        if(node.right != null){
            findAllSums(node.right, preDigit*10 + node.val, sums);
        }
    }
}