House Robber III

Problem

Houses form a binary tree instead of a line. A thief cannot rob a house AND its direct parent or child on the same night (robbing two DIRECTLY-connected houses trips the alarm — houses two levels apart are fine). Return the maximum amount robbable. (LeetCode 337.)

Examples

    3
   / \
  2   3
   \   \
    3   1

Constraints

up to 10⁴ nodes

Attempt it first

This is the module's true capstone: it fuses Module 17's top-down/ bottom-up tree recursion with THIS module's rob-or-skip DP thinking. The 1D House Robber problem's dp[i] = max(dp[i-1], dp[i-2] + nums[i]) worked because a house's only neighbors were its immediate array predecessors — but a tree node's "forbidden neighbors" are its CHILDREN, and a naive bottom-up recursion that returns just "the best achievable at this subtree" runs into exactly the trap Diameter of Binary Tree (Module 17) warned about: the value a PARENT needs from a child depends on whether the CHILD was robbed, and a single returned number can't convey that. Before opening anything, think about what a node needs to return to its parent so the parent can correctly decide its OWN rob-or-skip choice.