Tree Path Sum II Count

Problem

Count all downward paths in a binary tree that sum to a target value.

A path may start and end at any nodes but must always move from parent to child. tree is a level-order list with None marking missing nodes. Use prefix sums with backtracking: at each node count how many earlier prefix sums equal current_sum minus target.

Return the number of such paths.

Hint

Remove a prefix sum from the map when leaving a node so only the current root-to-node path counts.

Test cases

case 1

in: [[10,5,-3,3,2,null,11],8]

expected: 2

case 2

in: [[1,2,3],3]

expected: 2

case 3

in: [[],5]

expected: 0

case 4

in: [[5],5]

expected: 1

case 5

in: [[1],2]

expected: 0

Starter codePython

def count_paths_with_sum(tree, target):
    # Your code here
    pass

5 test cases · run your code against them in the editor