Java DP solution


  • 0
    D

    Each node holds all possible path sum that starts from itself and ends with each child node (including itself).

    public class Solution {
        public int pathSum(TreeNode root, int sum) {
            if (root == null) {
                return 0;
            }
            Map<TreeNode, List<Integer>> pathsums = new HashMap<>();
            calculate(root, pathsums);
            int paths = 0;
            for (List<Integer> list : pathsums.values()) {
                for (int pathsum : list) {
                    paths += pathsum == sum ? 1 : 0;
                }
            }
            return paths;
        }
    
        private void calculate(TreeNode root, Map<TreeNode, List<Integer>> pathsums) {
            pathsums.put(root, new ArrayList<Integer>());
            if (root.left == null && root.right == null) {
                pathsums.get(root).add(root.val);
                return;
            }
            pathsums.get(root).add(root.val);
            if (root.right != null) {
                calculate(root.right, pathsums);
                List<Integer> rightsums = pathsums.get(root.right);
                for (int rightsum : pathsums.get(root.right)) {
                    pathsums.get(root).add(root.val + rightsum);
                }
            }
            if (root.left != null) {
                calculate(root.left, pathsums);
                List<Integer> leftsums = pathsums.get(root.left);
                for (int leftsum : pathsums.get(root.left)) {
                    pathsums.get(root).add(root.val + leftsum);
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.