< 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.