1199. House Robber III — Tree DP

Houses form a binary tree (given in level-order with null for missing nodes). You cannot rob two directly-connected houses (parent and child). Return the maximum amount you can rob. The input is JSON {tree}.

Input: JSON {tree}.

Output: Integer — the maximum robbable amount.

Examples

Input: {"tree":[3,2,3,null,3,null,1]}
Output: 7
Explanation: Rob 3 + 3 + 1.

Input: {"tree":[3,4,5,1,3,null,1]}
Output: 9
Explanation: Rob 4 + 5.

Input: {"tree":[5]}
Output: 5
Explanation: Single house.

Constraints

• 1<=nodes<=10^4

Asked by