House Robber Iii - Leetcode Solution

Problem:

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 1: Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2: Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Constraints: The number of nodes in the tree is in the range [1, 10^4]. 0 <= Node.val <= 10^4

Solution:

This problem is a typical binary tree Dynamic Programming problem. We can define a function rob(root: TreeNode) -> int, where the root is the current node in the binary tree. This function returns two values — the maximum amount of money the thief can rob if he robs the current house and the maximum amount of money if he does not rob the current house.

Algorithm:

1. We define a recursive function called rob(root: TreeNode) -> (int, int) that takes input the current node in the binary tree. We need to consider two cases at each level:

• Case 1: Rob the current house. When the thief at the current node decides to rob the current house, he can no longer rob its children. Therefore, he can only rob the children of the left and right subtree of the children. Let us denote the maximum amount of money he can rob from the left and right subtree recursively as (left_with_root, left_without_root) and (right_with_root, right_without_root). Therefore, the maximum amount of money he can rob if he robs the current house + the maximum amount of money he can rob from its grandchildren can be calculated as root.val + left_without_root + right_without_root.

• Case 2: Do not rob the current house. When the thief at the current node decides to not rob the current house, he can either choose to rob or not rob its children. Thus, he can rob the maximum of the left_with_root and left_without_root or right_with_root and right_without_root subtree recursively. Therefore, the maximum amount of money he can rob if he does not rob the current house can be calculated as max(left_with_root, left_without_root) + max(right_with_root, right_without_root).

2. The base case of our recursive function is when the current node is None, which means that there are no more nodes and hence the maximum amount of money to rob is 0.

3. The final solution is the maximum of the result obtained when the current house is robbed and when it is not robbed. i.e. max(rob(root)[0], rob(root)[1]).

The time complexity of this algorithm is O(N) as we traverse the binary tree only once. The space complexity is O(H) where H is the height of the binary tree as the call stack can go as deep as H at each iteration of the recursive function.

Code: (Python)

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 rob_helper(root: TreeNode) -> (int, int): if not root: return (0, 0) left_with_root, left_without_root = rob_helper(root.left) right_with_root, right_without_root = rob_helper(root.right) # Case 1: Rob the current node rob_this_level = root.val + left_without_root + right_without_root # Case 2: Don't rob the current node not_rob_this_level = max(left_with_root, left_without_root) + max(right_with_root, right_without_root) return (not_rob_this_level, rob_this_level)

    return max(rob_helper(root))
    

Note: The above Python code is compatible with Python 3.6 or later versions.

1