222. House Robber III

For each node compute two numbers in one post-order pass: the best loot if we ROB this node (then its children must be skipped) and the best if we SKIP it (children are free to choose their own best). A parent combines its children's pairs; the answer is the max of the root's pair.

Two numbers per node

The police rule only forbids robbing a node and its direct child together. So at every node return a pair:

• rob = most money if we do rob this node,
• skip = most money if we don't rob this node.

Combining children

Let the left child return (lr, ls) and the right child (rr, rs).

• If we rob this node, we take its value and are forbidden from robbing either child, so both children must be skipped:

  rob = node.val + ls + rs
  

• If we skip this node, each child independently does whatever is best for it:

  skip = max(lr, ls) + max(rr, rs)
  

A null child returns (0, 0). Compute this bottom-up (post-order), and the answer is max(rob, skip) at the root.

Worked example

Tree [3, 2, 3, null, 3, null, 1]:

      3
     / \
    2   3
     \   \
      3   1

• Leaf 3 (under 2) → (3, 0). Leaf 1 (under right 3) → (1, 0).
• Node 2: rob = 2 + 0 = 2 (its only child skipped), skip = max(3,0) = 3 → (2, 3).
• Node right 3: rob = 3 + 0 = 3, skip = max(1,0) = 1 → (3, 1).
• Root 3: rob = 3 + skip_left(3) + skip_right(1) = 3 + 3 + 1 = 7; skip = max(2,3) + max(3,1) = 3 + 3 = 6. Answer max(7, 6) = 7.

Rob the two leaves (3, 3) and the root 3? No — rob the root (3) plus the two grandchildren (3 and 1): 3 + 3 + 1 = 7.

Complexity

• Time: O(n) — each node visited once.
• Space: O(h) recursion stack, h = tree height.

class Solution {
    public int rob(TreeNode root) {
        int[] ans = dfs(root);
        return Math.max(ans[0], ans[1]);
    }

    // returns {robThis, skipThis} for the subtree rooted at node.
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int robThis = node.val + left[1] + right[1];
        int skipThis = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{robThis, skipThis};
    }
}