NeetCode #451LC-337MediumTreesNC 250
← Back to All Problems#451 · #337 · House Robber III(打家劫舍 III)
📌 Problem Statement & Constraints
A thief plans to rob houses arranged in a binary tree. Adjacent houses (parent and child) cannot both be robbed. Return the maximum amount that can be robbed. Constraints: the number of nodes is in
[1, 10^4], 0 <= Node.val <= 10^4.💡 Core Algorithmic Approaches
- This is House Robber on a tree. For each node, two states matter: robbing it or skipping it.
- Return a pair
(rob, skip):rob = node.val + left.skip + right.skip, andskip = max(left.rob, left.skip) + max(right.rob, right.skip). - The answer at the root is
max(rob, skip). - This bottom-up DP is O(n) and avoids recomputing subproblems, unlike a naive recursion that considers grandchildren separately.
💻 Benchmark Python3 Implementation
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def dfs(node: Optional[TreeNode]):
"""Return (best if this node is robbed, best if it is not)."""
if not node:
return (0, 0)
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip # children must be skipped
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob, skip)
return max(dfs(root))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Returning a single value: the two states must be propagated, otherwise the parent cannot decide optimally.
- Computing
robwith the children'srobvalues: robbing a node forbids robbing its children, so theirskipvalues must be used. - Recursing into grandchildren explicitly: that gives O(n) states with O(n) work each, i.e. O(n^2) -- the two-state DP is what makes it linear.
- Assuming the root must be robbed: it may be better to skip it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.