House Robber III

NeetCode: House Robber III · LeetCode: 337. House Robber III · Difficulty: Medium

The houses form a binary tree. If two directly linked houses (a parent and its child) are both robbed, the police are alerted. Return the maximum amount you can rob without robbing two directly linked houses.

Example

Text

Input:  root = [3,2,3,null,3,null,1]
Output: 7      (rob 3 + 3 + 1)

Input:  root = [3,4,5,1,3,null,1]
Output: 9      (rob 4 + 5)

At every node there are only two choices: rob it, which forces you to skip both children (but you may take the grandchildren), or skip it, in which case each child subtree is solved independently.

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

The totals are int values. If the sum of house values could exceed the range of int, it would wrap silently and the method would need long.

Brute force: recursion over children and grandchildren

Let rob(node) be the best amount from the subtree at node. Then rob(node) = max(node.val + rob(each grandchild), rob(left) + rob(right)). This is correct, but rob(grandchild) is also reached through rob(child), so the same subtree is solved many times. The number of calls satisfies roughly T(n) = T(children) + T(grandchildren), which grows exponentially with the depth of the tree.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int withRoot = root.val;
        if (root.left != null) {
            withRoot += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            withRoot += rob(root.right.left) + rob(root.right.right);
        }
        int withoutRoot = rob(root.left) + rob(root.right);
        return Math.max(withRoot, withoutRoot);
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rob(tree(3, 2, 3, null, 3, null, 1)));
        System.out.println(s.rob(tree(3, 4, 5, 1, 3, null, 1)));
        System.out.println(s.rob(tree()));
    }
}

Output

7
9
0

Time: exponential in the height of the tree in the worst case. Space: O(h) recursion.

Better: memoise each subtree

The value of a subtree never changes, so compute it once and store it. TreeNode does not override equals or hashCode, so a HashMap<TreeNode, Integer> treats each node object as its own key (identity comparison), which is the key needed here. Each node is now solved once, so the work is O(n); the cost is an O(n) hash map.

Java

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private Map<TreeNode, Integer> memo;

    private int solve(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Integer cached = memo.get(root);
        if (cached != null) {
            return cached;
        }
        int withRoot = root.val;
        if (root.left != null) {
            withRoot += solve(root.left.left) + solve(root.left.right);
        }
        if (root.right != null) {
            withRoot += solve(root.right.left) + solve(root.right.right);
        }
        int withoutRoot = solve(root.left) + solve(root.right);
        int best = Math.max(withRoot, withoutRoot);
        memo.put(root, best);
        return best;
    }

    public int rob(TreeNode root) {
        memo = new HashMap<>();
        return solve(root);
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rob(tree(3, 2, 3, null, 3, null, 1)));
        System.out.println(s.rob(tree(3, 4, 5, 1, 3, null, 1)));
        System.out.println(s.rob(tree()));
    }
}

Output

7
9
0

Time: O(n). Space: O(n) for the map, plus O(h) recursion.

Optimal: return a (rob, skip) pair

Instead of caching by node, have each call return both answers for its subtree: the best if the root is robbed, and the best if the root is skipped. A two-element int[] carries the pair: index 0 is the robbed value and index 1 the skipped value. The parent combines them directly:

rob = node.val + left.skip + right.skip (children must be skipped)
skip = max(left.rob, left.skip) + max(right.rob, right.skip) (each child is free to do its best)

Each node is visited once and nothing is stored beyond the recursion stack. The answer is max(rob, skip) at the root.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    // Returns {best if root is robbed, best if root is skipped}.
    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[] {0, 0};
        }
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int rob = root.val + left[1] + right[1];
        int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[] {rob, skip};
    }

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

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rob(tree(3, 2, 3, null, 3, null, 1)));
        System.out.println(s.rob(tree(3, 4, 5, 1, 3, null, 1)));
        System.out.println(s.rob(tree()));
    }
}

Output

7
9
0

Time: O(n). Space: O(h) for the recursion (O(log n) balanced, O(n) for a chain).

Interview points

Robbing a node forces both children to be skipped; skipping it lets each child do its best.
Plain recursion over grandchildren repeats subtree work and is exponential in the height.
A memo map or a (rob, skip) pair per node brings the time to O(n).
The pair approach needs no map, only the recursion stack.

Summary

Recurrence: rob = val + left.skip + right.skip; skip = max(left) + max(right).
Memoisation uses an identity-keyed HashMap; the pair approach uses O(h) space.
An empty tree returns 0.