337. House Robber III #

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 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.

Problem Summary #

A new area where theft is possible has only one entrance, called the “root.” Except for the “root,” each house has exactly one “parent” house connected to it. After some reconnaissance, the smart thief realized that “the arrangement of all houses in this place is similar to a binary tree.” If two directly connected houses are robbed on the same night, the houses will automatically trigger the alarm. Calculate the maximum amount of money the thief can steal in one night without triggering the alarm.

Solution Ideas #

• This is the 3rd House Robber problem. In this problem, the houses to be robbed are tree-shaped. The condition for triggering the alarm is still that if adjacent houses are both robbed, the alarm will be triggered. It is just that here, adjacent houses are on the tree. The question asks for the maximum amount the thief can ultimately steal without triggering the alarm.
• The solution idea is DFS. Whether the current node is robbed will produce 2 outcomes. If the current node is robbed, then its child nodes can be robbed; if the current node is not robbed, then its child nodes cannot be robbed. Recursively follow this logic, eventually recurse to the root node, and take the maximum value as the output.

Code #

func rob337(root *TreeNode) int {
	a, b := dfsTreeRob(root)
	return max(a, b)
}

func dfsTreeRob(root *TreeNode) (a, b int) {
	if root == nil {
		return 0, 0
	}
	l0, l1 := dfsTreeRob(root.Left)
	r0, r1 := dfsTreeRob(root.Right)
	// The current node is not robbed
	tmp0 := max(l0, l1) + max(r0, r1)
	// The current node is robbed
	tmp1 := root.Val + l0 + r0
	return tmp0, tmp1
}