⚡Flashcard Drill➔
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

  1. This is House Robber on a tree. For each node, two states matter: robbing it or skipping it.
  2. Return a pair (rob, skip): rob = node.val + left.skip + right.skip, and skip = max(left.rob, left.skip) + max(right.rob, right.skip).
  3. The answer at the root is max(rob, skip).
  4. 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 rob with the children's rob values: robbing a node forbids robbing its children, so their skip values 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems