Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Question
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Solution
This problem can be solved using Depth-First Search (DFS) and Hashmap. Here is a Python solution:
class Solution:
def pathSum(self, root, target):
# define global return var
self.numOfPaths = 0
# 1st layer DFS to go through each node
self.dfs(root, target)
# return result
return self.numOfPaths
# define: traverse through the tree, at each treenode we will initiate a 2nd layer DFS to test if a path sum includes the answer
def dfs(self, node, target):
# exit condition
if node is None:
return
# 2nd layer DFS
self.test(node, target) # we know that node is not None
# next step
self.dfs(node.left, target)
self.dfs(node.right, target)
# define: for a given node, DFS to find any path that sum == target, if find self.numOfPaths += 1
def test(self, node, target):
# exit condition
if node is None:
return
if node.val == target:
self.numOfPaths += 1
# next step
self.test(node.left, target-node.val)
self.test(node.right, target-node.val)
This solution works by initiating a DFS from each node (1st layer DFS), then for each node we will test if there is a path (could start at any node that is the child of the current node and includes the current node) sum equals to the target (2nd layer DFS). If so, increment the global counter. The time complexity for this approach is O(N^2) for the worst case where the tree is a single path, and O(NlogN) for a balanced binary tree.
Similar Questions
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.A leaf is a node with no children. Example 1:Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22Output: trueExplanation: The root-to-leaf path with the target sum is shown.Example 2:Input: root = [1,2,3], targetSum = 5Output: falseExplanation: There two root-to-leaf paths in the tree:(1 --> 2): The sum is 3.(1 --> 3): The sum is 4.There is no root-to-leaf path with sum = 5.Example 3:Input: root = [], targetSum = 0Output: falseExplanation: Since the tree is empty, there are no root-to-leaf paths. Constraints:The number of nodes in the tree is in the range [0, 5000].-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Given a binary tree and an integer K. Find the number of paths in the tree which have their sum equal to K.A path may start from any node and end at any node in the downward direction.Since the answer may be very large, compute it modulo 109+7.
Given the root of a binary tree, return the sum of all left leaves.A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
The number of edges from the root to the node is called __________ of the tree
A binary search tree is generated by inserting in order the following integers: 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24, 49 The number of nodes in the left subtree and right subtree of the root respectively is a. (8, 4) b. (4, 7) c. (7, 4) d. (4, 8)
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.