Q337: House Robber III

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 forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

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.
Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

As in tree structure, we can say that the problem for the tree can be divided into problems of the left and right subtrees and once we get these subproblems out, we could merge them somehow to get the answer for the full tree.

It fits well for tree structure since we don’t need to worry about the issue of duplicated work. The root could either be robbed or not and the solution takes the better one among the two.

no_rob_val(node) = 
  max(rob_val(node.left), no_rob_val(node.left)) + 
  max(rob_val(node.right), no_rob_val(node.right))
rob_val(node) = node.val + no_rob_val(node.left) + no_rob_val(node.right)

From here, the first thought is to solve rob_val and no_rob_val separately. But the problem is that rob_val(node) and no_rob_val(node) generates duplicated recursion. More specifically, they ask for no_rob_val(node.left) and no_rob_val(node.right) twice.

OK, here comes the trick. We can solve the rob_val and no_rob_val in one calculation, simply we calculate no_rob_val(node.left) and no_rob_val(node.right) once and apply to both no_rob_val(node) and rob_val(node).

So, it becomes:

no_rob_val_left, rob_val_left = soln(node.left)
no_rob_val_right, rob_val_right = soln(node.right)
no_rob_val = 
  max(rob_val_left, no_rob_val_left) + 
  max(rob_val_right, no_rob_val_right)
rob_val = node.val + no_rob_val_left + no_rob_val_right

return no_rob_val, rob_val

The Python submission.

class Solution:
    def rob(self, root: TreeNode) -> int:
        norob_root, rob_soln = self.soln(root)
        return max(norob_root, rob_soln)
    def soln(self, node):
        if node is None:
            return 0, -float('inf')
        norob_soln_l, rob_soln_l = self.soln(node.left)
        norob_soln_r, rob_soln_r = self.soln(node.right)
        # if rob:
        res_rob = node.val + norob_soln_l + norob_soln_r
        # if not rob:
        res_norob = max(norob_soln_l, rob_soln_l) + max(norob_soln_r, rob_soln_r)
        return res_norob, res_rob