House Robber III

Problem

Houses are arranged in a binary tree. Adjacent nodes (connected by edge) cannot both be robbed. Find max robbery amount.

Key insight: Tree DP. Each node returns two values: (rob this node, skip this node). Then combine optimally.

Approach — Post-order DP returning pair

dfs(node) → (rob_this, skip_this)
rob_this = node.val + skip_left + skip_right
skip_this = max(rob_left, skip_left) + max(rob_right, skip_right)

Solutions

// C
int* dfs(TreeNode* node) {
    int* res = malloc(2 * sizeof(int));
    if (!node) { res[0] = res[1] = 0; return res; }
    int* l = dfs(node->left);
    int* r = dfs(node->right);
    res[0] = node->val + l[1] + r[1]; // rob this
    res[1] = (l[0]>l[1]?l[0]:l[1]) + (r[0]>r[1]?r[0]:r[1]); // skip this
    free(l); free(r);
    return res;
}
int rob(TreeNode* root) {
    int* res = dfs(root);
    int ans = res[0] > res[1] ? res[0] : res[1];
    free(res);
    return ans;
}

// C++
pair<int,int> dfs(TreeNode* node) {
    if (!node) return {0, 0};
    auto [rl, sl] = dfs(node->left);
    auto [rr, sr] = dfs(node->right);
    int rob = node->val + sl + sr;
    int skip = max(rl, sl) + max(rr, sr);
    return {rob, skip};
}
int rob(TreeNode* root) {
    auto [r, s] = dfs(root);
    return max(r, s);
}

// Java
public int rob(TreeNode root) {
    int[] res = dfs(root);
    return Math.max(res[0], res[1]);
}
int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] l = dfs(node.left), r = dfs(node.right);
    int robThis = node.val + l[1] + r[1];
    int skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
    return new int[]{robThis, skip};
}

// JavaScript
function rob(root) {
    function dfs(node) {
        if (!node) return [0, 0];
        const [rl, sl] = dfs(node.left);
        const [rr, sr] = dfs(node.right);
        return [node.val + sl + sr, Math.max(rl, sl) + Math.max(rr, sr)];
    }
    return Math.max(...dfs(root));
}

# Python
def rob(root):
    def dfs(node):
        if not node:
            return 0, 0  # (rob_this, skip_this)
        rl, sl = dfs(node.left)
        rr, sr = dfs(node.right)
        rob_this = node.val + sl + sr
        skip_this = max(rl, sl) + max(rr, sr)
        return rob_this, skip_this
    return max(dfs(root))

Complexity

Time: O(n)
Space: O(h)

Key Insight

Each node returns a pair: rob vs. skip. Parent combines children's pairs optimally — classic Tree DP pattern.