House Robber III

Problem Statement

Houses in a neighborhood are arranged in a binary tree structure. Each house has a certain amount of money, and directly connected houses (parent-child) have security systems linked. The robber cannot rob two directly linked houses on the same night. Return the maximum amount of money that can be robbed.

Approach

This is a classic tree DP problem. At each node, we have two choices:

1. Rob this node: Take its value, but must skip both children
2. Skip this node: Take the optimal from each subtree (which may or may not include robbing the children)

We return a pair (rob, skip) from each DFS call:

• rob: max money if we rob the current node
• skip: max money if we skip the current node