deepSWE.io

House Robber III

TreesDynamic Programming

Problem Statement

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the `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

Output: 7

Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Algorithm Explanation

This problem can be solved using dynamic programming on a tree. For each node, we need to decide whether to rob it or not. This decision affects the choices we can make for its children.

Algorithm Steps

DFS with a Pair: We'll use a recursive DFS function that returns a pair of values for each node: `[with_node, without_node]`. `with_node` is the maximum amount of money we can rob from the subtree including the current node, and `without_node` is the maximum amount without robbing the current node.
Base Case: If the node is null, we return `[0, 0]`.
Recursive Calls: We make recursive calls on the left and right children to get their `[with, without]` pairs.
Calculate `with_node`: If we rob the current node, we cannot rob its children. So, `with_node = node.val + left_without + right_without`.
Calculate `without_node`: If we don't rob the current node, we are free to either rob or not rob its children. We take the maximum of the two choices for each child: `without_node = max(left_with, left_without) + max(right_with, right_without)`.
Final Result: The final answer is the maximum of the `with` and `without` values for the root node.

Start

Starting DFS from the root.

With Node: 0

Without Node: 0

House Robber III Solution


class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        
        def dfs(node):
            if not node:
                return (0, 0)  # (with_node, without_node)
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            # If we rob the current node, we cannot rob its children
            with_node = node.val + left[1] + right[1]
            
            # If we don't rob the current node, we can take the max of robbing or not robbing its children
            without_node = max(left) + max(right)
            
            return (with_node, without_node)

        return max(dfs(root))