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.
思路：
- 对于每个node，我们如果选择偷，则最大值等于node.val和它的孙子层的所有节点最大值的和；如果不偷，最大值等于它的左右儿子节点的最大值之和。
- 由于从root开始向下搜索，越靠近底部的节点被重复计算的次数越多，因此可以用一个hashmap来记录底层已经计算过的节点，这样每个节点只会被计算一次。
public class HouseRobberIII {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
Map<TreeNode, Integer> map = new HashMap<>();
return robHelper(root, map);
}
private int robHelper(TreeNode root, Map<TreeNode, Integer> map) {
if (root == null) {
return 0;
}
if (map.containsKey(root)) {
return map.get(root);
}
int res = root.val;
if (root.left != null) {
res += robHelper(root.left.left, map) + robHelper(root.left.right, map);
}
if (root.right != null) {
res += robHelper(root.right.left, map) + robHelper(root.right.right, map);
}
int val = Math.max(res, robHelper(root.left, map) + robHelper(root.right, map));
map.put(root, val);
return val;
}
}
