Solution For Path Sum Iii
Problem Statement:
You are given a binary tree in which each node contains an integer value. Find 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).
Solution:
The problem can be approached using the concept of recursion. For each node, we can calculate the sum of all the paths that start at that node and reach any of its descendants. To do this, we need to consider two cases:
1) Include the current node in the path
2) Exclude the current node from the path
If we include the current node in the path, then we need to pass the remaining sum (sum – node.val) to its children for further processing. If we exclude the current node from the path, then we just need to pass the original sum to its children.
We can implement this using a recursive function that takes the current node, the target sum, and the current sum as input. At each iteration, we check if the current sum equals the target sum. If yes, we increment the counter for the number of paths. Then, we process the left and right children of the current node using the above logic.
Code:
“`
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
self.count = 0
self.dfs(root, sum, [])
return self.count
def dfs(self, node, target, path):
if node is None:
return
path.append(node.val)
curr_sum = 0
for i in range(len(path)-1, -1, -1):
curr_sum += path[i]
if curr_sum == target:
self.count += 1
self.dfs(node.left, target, path)
self.dfs(node.right, target, path)
path.pop()
“`
Explanation:
In the code above, we have defined a recursive function called dfs that takes three arguments:
1) node – the current node being processed
2) target – the target sum
3) path – a list of the values in the path from the root to the current node
We initialize the count of paths to 0 and call the dfs function with the root node, target sum, and an empty path.
In the dfs function, we first check if the current node is None, in which case we return. Otherwise, we add the current node’s value to the path and initialize a variable called curr_sum to 0. We then loop through the path list from the end to the start and calculate the sum of all the values in the path from the current node to any of its ancestors. If this sum equals the target sum, we increment the counter for the number of paths.
We then recursively call the dfs function with the left child and right child of the current node, passing the target sum and the current path. After processing the children, we remove the current node’s value from the path list to backtrack and explore other paths.
At the end of the recursion, we return the count of paths.
Step by Step Implementation For Path Sum Iii
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
// pathSumStartHere will return the total number of paths that start at the current node
// and sum up to the given value.
int pathSumStartHere = findPathSum(root, sum);
// We also need to check paths that start from the left and right child of the current node.
int pathSumLeft = pathSum(root.left, sum);
int pathSumRight = pathSum(root.right, sum);
// The total number of paths is the sum of the three numbers we just calculated.
return pathSumStartHere + pathSumLeft + pathSumRight;
}
// This helper function will return the total number of paths that start at the given node
// and sum up to the given value.
private int findPathSum(TreeNode node, int sum) {
if (node == null) {
return 0;
}
// We need to check if the current node's value is equal to the given sum.
// If it is, that means we've found a path that sums up to the given value.
int pathSum = 0;
if (node.val == sum) {
pathSum++;
}
// We also need to check the left and right child of the current node.
pathSum += findPathSum(node.left, sum - node.val);
pathSum += findPathSum(node.right, sum - node.val);
return pathSum;
}
}# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
# Edge case:
if not root:
return 0
# Helper function to find the number of paths with a given sum
# starting from a given node:
def pathSumFrom(node, target):
# Base case:
if not node:
return 0
# Recursive case:
# If the current node has a value that equals the target,
# then we've found a path with the given sum:
if node.val == target:
pathCount = 1
else:
pathCount = 0
# Check if there are any paths with the given sum
# in the subtrees of the current node:
pathCount += pathSumFrom(node.left, target - node.val)
pathCount += pathSumFrom(node.right, target - node.val)
return pathCount
# Initialize path count:
pathCount = 0
# Find the number of paths with the given sum
# starting from the root node:
pathCount += pathSumFrom(root, sum)
# Find the number of paths with the given sum
# in the subtrees of the root node:
pathCount += self.pathSum(root.left, sum)
pathCount += self.pathSum(root.right, sum)
return pathCountvar pathSum = function(root, sum) {
// base case - if the root is null, then there are no paths
if (!root) {
return 0;
}
// recursive case 1 - check if there is a path from the current node to any child
let pathFromRoot = pathSumFrom(root, sum);
// recursive case 2 - check if there is a path from any of the child nodes to the root
let pathToRoot = pathSum(root.left, sum) + pathSum(root.right, sum);
return pathFromRoot + pathToRoot;
};
function pathSumFrom(node, sum) {
// base case - if the node is null, then there is no path
if (!node) {
return 0;
}
// recursive case 1 - check if the current node is equal to the sum
let pathFromNode = 0;
if (node.val === sum) {
pathFromNode = 1;
}
// recursive case 2 - check if there is a path from the current node to any child
let pathToChild = pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
return pathFromNode + pathToChild;
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if (!root)
return 0;
return pathSumFrom(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}
int pathSumFrom(TreeNode* node, int sum) {
if (!node)
return 0;
return (node->val == sum ? 1 : 0)
+ pathSumFrom(node->left, sum - node->val) + pathSumFrom(node->right, sum - node->val);
}
};/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int PathSum(TreeNode root, int sum) {
//base case
if(root == null){
return 0;
}
//recursive case
return PathSumFrom(root, sum) + PathSum(root.left, sum) + PathSum(root.right, sum);
}
public int PathSumFrom(TreeNode node, int sum){
//base case
if(node == null){
return 0;
}
//recursive case
return (node.val == sum ? 1 : 0)
+ PathSumFrom(node.left, sum - node.val)
+ PathSumFrom(node.right, sum - node.val);
}
}