A company's departments form a binary tree; each node has an integer budget (which may be negative, representing a credit). The total budget of a department is the sum of the budgets of that department and all of its sub-departments (its subtree). Given a target amount, report how many departments have a total budget exactly equal to the target.
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer budget or null for a missing child. Children of null nodes are omitted.
Line 3: an integer target.
A single integer: the number of departments whose total budget equals target.
target is between -2000000000 and 2000000000.Example 1
Input
3 1 -1 1 1
Expected
2
Explanation
Subtree totals: the left leaf is -1, the right leaf is 1, and the whole tree is 1 + (-1) + 1 = 1. Two of them equal the target 1: the right leaf and the whole tree.
Example 2
Input
3 5 3 8 8
Expected
1
Explanation
Subtree totals: leaf 3, leaf 8, and root 5 + 3 + 8 = 16. Only the right leaf equals 8, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →