We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

House Robber III

Difficulty: Medium

Problem Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Each house has one and only one parent house, forming a binary tree. The police will be alerted if two directly-linked houses are broken into on the same night. Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Key Insights

  • The problem can be solved using a tree traversal method, specifically Depth-First Search (DFS).
  • We need to consider two scenarios for each node: robbing the current node and skipping its children, or skipping the current node and potentially robbing its children.
  • Dynamic programming can be utilized to store the maximum amounts we can rob from subtrees to avoid recomputing values.
  • Each node can be represented with two values: the maximum amount robbed if the node is robbed and if it is not robbed.

Space and Time Complexity

Time Complexity: O(n) - Each node is visited once. Space Complexity: O(h) - The space complexity is primarily due to the recursion stack, where h is the height of the tree.

Solution

To solve the problem, we can utilize a Depth-First Search (DFS) approach with dynamic programming. For each node in the tree, we will calculate two values:

  1. The maximum money that can be robbed if the current node is included (which means we cannot include its children).
  2. The maximum money that can be robbed if the current node is excluded (allowing us to include its children).

We will keep a helper function that returns these two values as a tuple.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root: TreeNode) -> int:
    def dfs(node):
        if not node:
            return (0, 0)  # (money if robbed, money if not robbed)
        
        left = dfs(node.left)
        right = dfs(node.right)
        
        # If we rob this node, we cannot rob its children
        money_if_robbed = node.val + left[1] + right[1]
        # If we don't rob this node, we can rob its children
        money_if_not_robbed = max(left) + max(right)
        
        return (money_if_robbed, money_if_not_robbed)
    
    return max(dfs(root))
← Back to All Questions