Binary Tree Path Sum Count

Given a binary tree and an integer target sum \(T\), count the number of paths in the tree whose node values sum to \(T\). A path is defined as a sequence of nodes starting from any node and moving only downward (from parent to child). The path does not need to start at the root or end at a leaf.

For a path consisting of nodes \(n_1, n_2, \ldots, n_k\), the condition to be satisfied is:

[ n_1 + n_2 + \cdots + n_k = T ]

Your task is to implement a program that reads the target sum and the binary tree (given in level-order, where "null" indicates missing nodes) from standard input, and outputs the number of paths that sum to \(T\) to standard output.

inputFormat

The input is given in two parts:

1. The first line contains an integer \(T\), the target sum.
2. The second line contains the level-order representation of the binary tree with node values separated by spaces. Use the token "null" for missing nodes. If the tree is empty, the second line will be "null".

outputFormat

Output a single integer representing the number of paths in the binary tree that sum to the target \(T\).

8
10 5 -3 3 2 null 11 3 -2 null 1

3