Related: LeetCode - Path Sum
Related: LeetCode 437 - Path Sum III
https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2004.%20Trees%20and%20Graphs/Q4_12_Paths_with_Sum
Related: LeetCode 437 - Path Sum III
https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2004.%20Trees%20and%20Graphs/Q4_12_Paths_with_Sum
You are given a binary tree in which each node contains an integer value (which
might be positive or negative). Design an algorithm to count the number of paths that sum to a
given value. The path does not need to start or end at the root or a leaf, but it must go downwards
(traveling only from parent nodes to child nodes).
int countPathsWithSum(TreeNode root, int targetSum) {
return countPathsWithSum(root, targetSum, 0, new HashMap<Integer, Integer>());
}
int countPathsWithSum(TreeNode node, int targetSum, int runningSum,
HashMap<Integer, Integer> pathCount) {
if (node == null) return 0; // Base case
/* Count paths with sum ending at the current node. */
runningSum += node.data;
int sum= runningSum - targetSum;
int totalPaths = pathCount.getOrDefault(sum, 0);
/* If runningSum equals targetSum, then one additional path starts at root.
* Add in this path.*/
if (runningSum == targetSum) {
totalPaths++;
}
/* Increment pathCount, recurse, then decrement pathCount. */
incrementHashTable(pathCount, runningSum, 1); // Increment pathCount
totalPaths += countPathsWithSum(node.left, targetSum, runningSum, pathCount);
totalPaths += countPathsWithSum(node.right, targetSum, runningSum, pathCount);
incrementHashTable(pathCount, runningSum, -1); // Decrement pathCount
return totalPaths;
}
void incrementHashTable(HashMap<Integer, Integer> hashTable, int key, int delta) {
int newCount = hashTable.getOrDefault(key, 0) + delta;
if (newCount == 0) {//Remove when zero to reduce space usage
hashTable.remove(key);
} else {
hashTable.put(key, newCount);
}
}
Brute Force - O(nlogn)
int countPathsWithSum(TreeNode root, int targetSum) {
if (root == null) return 0;
/* Count paths with sum starting from the root. */
int pathsFromRoot = countPathsWithSumFromNode(root, targetSum, 0);
/* Try the nodes on the left and right. */
int pathsOnleft = countPathsWithSum(root.left, targetSum);
int pathsOnRight = countPathsWithSum(root.right, targetSum);
return pathsFromRoot + pathsOnLeft + pathsOnRight;
}
int countPathsWithSumFromNode(TreeNode node, int targetSum, int currentSum) {
if (node == null) return 0;
currentSum += node.data;
int totalPaths = 0;
if (currentSum == targetSum) { // Found a path from the root
totalPaths++;
}
totalPaths += countPathsWithSumFromNode(node.left, targetSum, currentSum);
totalPaths += countPathsWithSumFromNode(node.right, targetSum, currentSum);
return totalPaths;
}
