House Robber III

medium tree dp dfs

Problem

Houses are arranged as a binary tree. Two directly-linked houses cannot both be robbed in the same night. Return the maximum amount of money you can rob.

Inputroot = [3,2,3,null,3,null,1]

Output7

Rob the root (3) plus the two grandchildren (3 + 1) — totals 7.

tree (level-order, use null)

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)
        l_rob, l_skip = dfs(node.left)
        r_rob, r_skip = dfs(node.right)
        rob_here = node.val + l_skip + r_skip
        skip_here = max(l_rob, l_skip) + max(r_rob, r_skip)
        return (rob_here, skip_here)
    return max(dfs(root))

function rob(root) {
  function dfs(node) {
    if (!node) return [0, 0];
    const [lr, ls] = dfs(node.left);
    const [rr, rs] = dfs(node.right);
    const robHere = node.val + ls + rs;
    const skipHere = Math.max(lr, ls) + Math.max(rr, rs);
    return [robHere, skipHere];
  }
  return Math.max(...dfs(root));
}

class Solution {
    public int rob(TreeNode root) {
        int[] r = dfs(root);
        return Math.max(r[0], r[1]);
    }
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int robHere = node.val + l[1] + r[1];
        int skipHere = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{robHere, skipHere};
    }
}

class Solution {
public:
    pair<int,int> dfs(TreeNode* node) {
        if (!node) return {0, 0};
        auto l = dfs(node->left);
        auto r = dfs(node->right);
        int robHere = node->val + l.second + r.second;
        int skipHere = max(l.first, l.second) + max(r.first, r.second);
        return {robHere, skipHere};
    }
    int rob(TreeNode* root) {
        auto p = dfs(root);
        return max(p.first, p.second);
    }
};

Explanation

Now the houses form a binary tree, and you can't rob a node together with either of its children. The neat idea is that each node returns two answers at once: the best total if we rob this node, and the best if we skip it.

We use a post-order DFS: solve both children first, then combine. From the left child we get (l_rob, l_skip) and from the right (r_rob, r_skip).

If we rob the current node, its children must be skipped, so rob_here = node.val + l_skip + r_skip. If we skip it, each child is free to do whatever is best, so skip_here = max(l_rob, l_skip) + max(r_rob, r_skip).

Returning the pair upward means every node is visited just once — no repeated work. At the root, the answer is simply the larger of its two values.

Example: tree [3,2,3,null,3,null,1]. Robbing the root 3 forces skipping its children but lets us take the two grandchildren 3 and 1, giving 3 + 3 + 1 = 7.

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