892. Find Pairs with Given Sum in BST

Given the root of a binary search tree and a target value, count the number of unordered pairs of distinct nodes whose values add up to the target. Since BST keys are distinct, each pair is counted once. The input gives a level-order BST array and the target separated by ' | '.

Input: A level-order BST array and the target, separated by ' | '.

Output: Integer — the number of qualifying pairs.

Examples

Input: [5,3,6,2,4,null,7] | 9
Output: 3
Explanation: Pairs (2,7), (3,6), and (4,5) each sum to 9.

Input: [5,3,6,2,4,null,7] | 28
Output: 0
Explanation: No qualifying pairs.

Input: [2,1,3] | 4
Output: 1
Explanation: Only (1,3).

Constraints

• 0<=nodes<=10^4
• valid BST

Asked by