916. House Robber III — Tree DP

Given the root of a binary tree where each node holds an amount of money, a thief cannot rob two directly-connected (parent-child) houses on the same night. Return the maximum total amount that can be robbed. The tree is given as a level-order array with null for missing children.

Input: A level-order array of the tree.

Output: Integer — the maximum robbed amount.

Examples

Input: [3,2,3,null,3,null,1]
Output: 7
Explanation: Rob 3 + 3 + 1 = 7.

Input: [3,4,5,1,3,null,1]
Output: 9
Explanation: Rob 4 + 5 = 9.

Input: [1]
Output: 1
Explanation: Rob the single house.

Constraints

• 1<=nodes<=10^4
• 0<=value<=10^4

Asked by