All problems

Downward Paths With a Given Sum

Medium · tree dfs

You are given the root of a binary tree and an integer target_sum.

A downward path starts at any node, then moves from a node to one of its children, again and again, and may stop at any node. It never turns back up. A single node on its own is a downward path.

Return how many downward paths have node values that add up to target_sum. Paths are told apart by the nodes they use, so two different paths with the same values are counted separately. An empty tree has no paths, so the answer is 0.

Examples

Example 1

Input: root = [5, 3, 2, 1, 4, null, 7], target_sum = 7

Output: 3

The paths 3 -> 4, 5 -> 2 and the single node 7 each add up to 7.

Example 2

Input: root = [1, 1, 1], target_sum = 2

Output: 2

The two paths are the root with its left child and the root with its right child.

Example 3

Input: root = [0, 1, 1], target_sum = 1

Output: 4

Each 1 on its own is a path, and so is the root followed by either 1, since the root is 0.

Constraints