algoadvance

The problem “House Robber III” can be found on LeetCode:

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were 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.

Example:

Input: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Clarifying Questions

  1. Input Constraints:
    • Is it guaranteed that the input will always be a valid binary tree?
    • Are the values of nodes non-negative integers?
  2. Edge Cases:
    • What should be returned if the tree is empty?

Strategy

To solve this problem, we can use a recursive approach with memoization to enhance the performance:

  1. Recursive Helper Function:
    • Define a helper function that returns two values:
      • The maximum amount of money we can rob including the current node.
      • The maximum amount of money we can rob excluding the current node.
  2. Recursive Cases:
    • If we include the current node, we cannot include its immediate children, but we can include the grandchildren.
    • If we exclude the current node, we can freely consider the children nodes.
  3. Memoization:
    • To avoid recomputation, use a dictionary to store the results of subproblems (values for each node).

Code

Here’s a Python implementation of the strategy described:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def rob(self, root: TreeNode) -> int:
        def helper(node):
            if not node:
                return (0, 0)
            
            # Post-order traversal to solve the problem bottom-up
            left = helper(node.left)
            right = helper(node.right)
            
            # If we rob the current node, we cannot rob its direct children
            rob_current = node.val + left[1] + right[1]
            
            # Otherwise, we take the max of robbing or not robbing each child
            not_rob_current = max(left) + max(right)
            
            return (rob_current, not_rob_current)
        
        # Calculate the maximum money that can be robbed starting from root
        return max(helper(root))

# Example Usage
# Construct the example tree [3,2,3,null,3,null,1]
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(3)
root.right.right = TreeNode(1)

solution = Solution()
print(solution.rob(root))  # Output: 7

Time Complexity

This solution efficiently calculates the maximum amount of money that can be robbed following the given constraints.

Try our interview co-pilot at AlgoAdvance.com