Aug 12, 2021

Leetcode 437 Path Sum III

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

image




Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

  • This question can be solved by Depth First Search.

  • We want to find all possible path that sum to the given number. Since the path does not have to start from the root, so any node can be the start of the path. We need to try every node to be the root and find if there is path from that root that sum up to the given number.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
            if not root: return 0
            def dfs(root, sum):
                res = 0
                if not root: return res
                if sum == root.val:
                    res += 1
                res += dfs(root.left, sum-root.val)
                res += dfs(root.right, sum-root.val)
                return res
            return dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)