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;
}
}