Imbalance score: hints, no solution
Medium · Trees
Each node of a binary reporting tree holds the number of tickets that person closed this month. A team's total is the sum of the tickets of every person in it, counting the manager and everyone below.
The tree is given in level order: the root first, then the children of each present node from left to right, with null standing for a missing child. Nodes below a missing child are not listed.
The imbalance of one manager is the absolute difference between the total of the left team and the total of the right team, where a missing team counts as 0. Return the imbalance score of the whole tree: the sum of the imbalance of every person in it, leaves included. A leaf has imbalance 0 and an empty tree scores 0.
Examples
- Input
- tree = [3, 5, 2, 1]
- Output
- 5
- Note
- Root: left team 6, right team 2, so 4. Employee 5: left 1, right 0, so 1. The others add 0. Total 5.
- Input
- tree = [4, 2, 2]
- Output
- 0
- Note
- Both teams total 2 at the root, and the two leaves add nothing.
Constraints
- 0 <= number of employees <= 2000
- Ticket counts are integers from 0 to 100
- The answer fits comfortably in a 64-bit integer
Hint 1: a nudge
For one manager, which two numbers about the people below them do you need to compute their imbalance?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.