Leetcode 437. Path Sum III (Python)

Related Topic

Depth-First-Search. Tree. Preorder-Traversal.

Description

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

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Sample I/O

Example 1

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Methodology

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.

Code(DFS)

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)

BigO

We traversal all nodes of the tree once so O(n) and we need to append each root value to the answer which takes O(n) so total is O(n^2)