All problems

Mentor Pairs

Medium · tree dp

A company is starting a mentoring programme. Its org chart is a binary tree: the head of the company is the root, and every employee has at most two direct reports, a left one and a right one. Each employee has a whole-number rating, which can be negative for someone who is struggling.

A mentoring pair is an employee and one of their direct reports. Every employee can be in at most one pair, and you may form as many pairs as you like, including none. The score of a pair is the sum of the two ratings, and the score of a programme is the sum of the scores of its pairs.

Return the highest score a programme can reach. If no pair is worth forming, the answer is 0.

Examples

Example 1

Input: root = [5, 3, 4]

Output: 9

The head can be paired with only one of the two reports. Pairing with the 4 scores 5 + 4 = 9, better than 5 + 3 = 8.

Example 2

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

Output: 10

The org chart is a single chain 1, 2, 3, 4. Pairs (1, 2) and (3, 4) score 3 + 7 = 10, more than the single pair (2, 3) which scores 5.

Example 3

Input: root = [-5, -2, -3]

Output: 0

Every pair would lower the score, so form none.

Constraints