Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 337 House Robber III - Problem Statement

LeetCode 337

Houses form a binary tree. Each house has money. You cannot rob two directly connected houses (parent and child). Find the maximum money you can rob. Example: Tree [3,2,3,null,3,null,1][3, 2, 3, \text{null}, 3, \text{null}, 1].

If you rob the root (33), you cannot rob its children (22 and 33). The best is 3+3+1=73+3+1=7: take the root and two grandchildren. This is House Robber on a tree. For each node, you decide: rob it or skip it?