House Robber III
Implement robTree
A binary tree of house values is given, and no two directly-connected houses (a parent and its own child) can both be robbed. Maximize the total value robbed. The tree is given as three parallel arrays —
values, plus each node's left and right child index (or -1 for no child) — with the root always at index 0.
At any node there are exactly two live possibilities: rob it (its children are off-limits, but its grandchildren aren't) or skip it (its children are free to be robbed or not, independently). Solving that naively re-derives the same subtree's answer over and over from different angles. The fix is to have every node hand back both of its own answers at once — best-if-robbed and best-if-skipped — computed bottom-up from its children's own pairs. A node's robbed value only needs its children's skipped values; its skipped value takes whichever of each child's two values is larger. One pass, root to leaves and back, settles the whole tree.
Example 1:
Input: values = [3,2,3,3,1], left = [1,-1,-1,-1,-1], right = [2,3,4,-1,-1]
Output: 7
Example 2:
Input: values = [3,4,5,1,3,1], left = [1,3,-1,-1,-1,-1], right = [2,4,5,-1,-1,-1]
Output: 9
Example 3:
Input: values = [5], left = [-1], right = [-1]
Output: 5
+ 6 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ values.length ≤ 100 (number of nodes; 0 means an empty tree) - ●
0 ≤ values[i] ≤ 10000 - ●
left[i] and right[i] hold the index of that node's left/right child, or -1 if it has none - ●
the tree's root is always at index 0 when values is non-empty
values =
[3, 2, 3, 3, 1]
left =
[1, -1, -1, -1, -1]
right =
[2, 3, 4, -1, -1]