House Robber III
The briefingthe full drill, in my own words
The drill: Every house sits in a binary tree, and robbing a house auto-alerts its direct parent and children — pick the take-free subset of houses worth the most, tree-shaped instead of a line.
Houses sit as nodes in a binary tree, each holding some amount of loot, and robbing any house instantly alerts its direct parent and its direct children.
Two houses connected by a single edge can never both be robbed on the same night, but two houses two edges apart are perfectly safe together — the ban only covers immediate parent-child pairs.
The goal is picking the subset of houses that avoids every such adjacent pair while banking the largest possible total, and returning that maximum total.
- loot values are non-negative on this course
- tree sizes run up to tens of thousands of nodes
- only direct parent-child pairs conflict — grandparents are safe together
- the answer is a single maximum total, not the house list
The hintstake only what you need
HINT 1 THE NUDGE
At every node you're really choosing between two totals: rob this house (its children are off-limits) or skip it (its children are fair game). Which total propagates upward depends on what the parent decides.
HINT 2 THE STRUCTURE
A node can't know whether to rob itself until it knows both outcomes for each child — robbed and not-robbed — not just one merged number.
HINT 3 ONE STEP FROM THE ANSWER
Postorder DFS returning a pair (robThis, skipThis): robThis = node.val + both children's skip values; skipThis = sum of max(rob, skip) per child. The answer is max of the pair at the root.
Coach's boardthe pattern, step by step
Robbing a house bans its direct parent and children only. Postorder gives each node both outcomes before its parent needs them.
The splitstwo paces, two languages
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def dfs(node: Optional[TreeNode]):
if not node:
return (0, 0) # (rob this, skip this)
rob_l, skip_l = dfs(node.left)
rob_r, skip_r = dfs(node.right)
rob_this = node.val + skip_l + skip_r
skip_this = max(rob_l, skip_l) + max(rob_r, skip_r)
return (rob_this, skip_this)
return max(dfs(root))class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
rob_root = root.val
if root.left:
rob_root += self.rob(root.left.left) + self.rob(root.left.right)
if root.right:
rob_root += self.rob(root.right.left) + self.rob(root.right.right)
not_rob_root = self.rob(root.left) + self.rob(root.right)
return max(rob_root, not_rob_root)class Solution {
public int rob(TreeNode root) {
int[] result = dfs(root);
return Math.max(result[0], result[1]);
}
// returns { robThis, skipThis }
private int[] dfs(TreeNode node) {
if (node == null) {
return new int[] { 0, 0 };
}
int[] l = dfs(node.left);
int[] r = dfs(node.right);
int robThis = node.val + l[1] + r[1];
int skipThis = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[] { robThis, skipThis };
}
}class Solution {
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
int robRoot = root.val;
if (root.left != null) {
robRoot += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
robRoot += rob(root.right.left) + rob(root.right.right);
}
int notRobRoot = rob(root.left) + rob(root.right);
return Math.max(robRoot, notRobRoot);
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED