< Back




337. House Robber III

We're robbing houses, again. This time, the houses are connected like a binary tree, and we can't
rob a house and then rob its children, otherwise we'll set off the alarms. We're asked to find the
maximum amount of money we can make without setting off the alarm.

Like every dynamic programming question, we have states and choices. In this case, we have two
states and two choices. States:

  * The current house
  * If the parent house was robbed

Choices:

  * Skip robbing the current house
  * Rob the current house

For our recursion, our base case returns 0 if we reach an empty node - visiting the child node of a
leaf node. During each recusive step, we'll check to see if the parent node was robbed. If so, we
skip robbing the current node and immediately travel to the left and right nodes. We also set the
state for our children to False for robbing the parent node, since this node hasn't been robbed.

If the parent node hasn't been robbed, we can either rob this node or skip this node. We take the
max out of the two outcomes.

The solution is as follows:


  class Solution:
      def rob(self, root: Optional[TreeNode]) -> int:
          @cache
          def dp(node: Optional[TreeNode], prev: bool) -> int:
              if not node:
                  return 0

              if prev:
                  return dp(node.left, False) + dp(node.right, False)
              else:
                  return max(
                      dp(node.left, True) + dp(node.right, True) + node.val,
                      dp(node.left, False) + dp(node.right, False),
                  )

          return dp(root, False)


_ Time Complexity:

  O(n) - We visit each node once, and the memoization helps us avoid recalculating or revisiting
  nodes unnecessarily.

_ Space Complexity:

  O(n) - The recursive call stack can reach size n.