284. House Robber III
A thief has found a neighborhood shaped like a binary tree: every house is a node, root is the single entrance, and each house's value is the cash inside. The security system links every house directly to its parent and children — robbing two houses that share a direct connection on the same night trips the alarm system.
Given the root of the tree, return the maximum total cash the thief can collect without ever robbing a parent and one of its children together. Houses that are not adjacent (for example a node and its grandchild) may both be robbed.
Example 1:
Input: root = [3, 2, 3, null, 3, null, 1]
Output: 7
Explanation: Rob the root (3) and the two grandchildren (3 and 1). No two robbed houses share an edge, and 3 + 3 + 1 = 7 is the best possible.
Example 2:
Input: root = [3, 4, 5, 1, 3, null, 1]
Output: 9
Explanation: Skipping the root and robbing both of its children, 4 + 5 = 9, beats robbing the root with any combination of grandchildren.
Constraints:
- 1 ≤ number of houses ≤ 10⁴
- 0 ≤ house value ≤ 10⁴
Hints:
For any single house there are only two possibilities: it gets robbed or it doesn't. If it is robbed, its children must be skipped — but its grandchildren become available again.
Writing rob(node) = max(node.val + rob(grandchildren), rob(children)) recomputes the same subtrees over and over. Either memoize per node, or have the DFS return richer information.
Have each node return a pair (best if this node IS robbed, best if it is NOT). Each is computable from the children's pairs in O(1), so one post-order pass solves the whole tree.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 2, 3, null, 3, null, 1]
Expected output: 7