A downward path is any non-empty sequence of nodes that starts at some node and repeatedly moves to a child (always going down). Given an integer k, count how many downward paths have node values that sum to exactly k. Paths that start at different nodes are counted separately even if they share values.
Input format
One line: the binary tree as a level-order array.
The tree is encoded on ONE line as a space-separated level-order (breadth-first) array. The token null marks a missing child; the children of a null are omitted from the array. An empty tree is written as the single token null.
The next line: an integer k.
Output format
A single integer: the number of downward paths whose values sum to k.
Constraints
- The tree has between 0 and 1000 nodes.
- Each node value is an integer with absolute value at most 1000.
- k is an integer with absolute value at most 1000000.