# 337. House Robber III (Medium)

https://leetcode.com/problems/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.
```

## Solutions

``````class Solution {

// Keep the maximum amount of money starting from specific node. You must distinguish following
// two situations.

// FIXME

// if node can be robbed
Map<TreeNode, Integer> robNodeMaxMoney = new HashMap<>();

// if node cannot be robbed
Map<TreeNode, Integer> noRobNodeMaxMoney = new HashMap<>();

public int rob(TreeNode root) {
if (root == null) {
return 0;
}

return recurse(root, true);
}

private int recurse(TreeNode root, boolean canRob) {
// return 0 if reach the end
if (root == null) {
return 0;
}

if (canRob && robNodeMaxMoney.containsKey(root)) {
return robNodeMaxMoney.get(root);
}
if (!canRob && noRobNodeMaxMoney.containsKey(root)) {
return noRobNodeMaxMoney.get(root);
}

// not rob, the max money from left branch
int max1 = 0;

// not rob, the max money from right branch
int max2 = 0;

// rob, the max money from left branch
int max3 = 0;

// rob, the max money from right branch
int max4 = 0;

int ans = 0;

// if parent node robbed, current one cannot be robbed
if (!canRob) {
max1 = Math.max(recurse(root.left, true), max1);
max2 = Math.max(recurse(root.right, true), max2);

ans = max1 + max2;

// choose the best robbing scheme for current node
noRobNodeMaxMoney.put(root, ans);
}
// if parent node not robbed, for current one you can choose rob or not.
else {
// you can rob but you give up
max1 = Math.max(recurse(root.left, true), max1);
max2 = Math.max(recurse(root.right, true), max2);

// you can rob and you do rob
max3 = Math.max(recurse(root.left, false), max3);
max4 = Math.max(recurse(root.right, false), max4);

// + root.val means rob current node
ans = Math.max(max1 + max2, max3 + max4 + root.val);

// choose the best robbing scheme for current node
robNodeMaxMoney.put(root, ans);
}

// return
return ans;
}
}
``````