Path Sum III – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem – Path Sum III – Leetcode Challenge – Java Solution.
Source – qiyuangong’s repository.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/*public int pathSum(TreeNode root, int sum) {
if (root != null) return findPaths(root, sum)
+ pathSum(root.left, sum)
+ pathSum(root.right, sum);
return 0;
}
private int findPaths(TreeNode root, int target) {
if (root != null) return (root.val == target? 1 : 0)
+ findPaths(root.left, target - root.val)
+ findPaths(root.right, target - root.val);
return 0;
}*/
private int result;
private HashMap cache;
public int pathSum(TreeNode root, int sum) {
result = 0;
cache = new HashMap();
cache.put(0, 1);
pathSumHelper(root, sum, 0);
return result;
}
// https://leetcode.com/problems/path-sum-iii/discuss/91892/Python-solution-with-detailed-explanation
private void pathSumHelper(TreeNode root, int target, int soFar) {
if (root != null) {
int complement = soFar + root.val - target;
if (cache.containsKey(complement))
result += cache.get(complement);
cache.put(soFar + root.val, cache.getOrDefault(soFar + root.val, 0) + 1);
pathSumHelper(root.left, target, soFar + root.val);
pathSumHelper(root.right, target, soFar + root.val);
cache.put(soFar + root.val, cache.get(soFar + root.val) - 1);
}
}
}
