Knowee
Questions
Features
Study Tools

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).

🧐 Not the exact question you are looking for?Go ask a question

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.

This problem has been solved

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)

1/3

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.