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:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
Solution：[DP思想] 遞歸 Post-order 分治 Bottom-up向上傳遞
思路：
DP思路和 198. House Robber 思路一樣
實(shí)現(xiàn)：分治左右樹在跳，分別得到左/右子樹 的 含cur_max/不含prev_max 相鄰結(jié)點(diǎn)的 最大值符隙，在當(dāng)前結(jié)點(diǎn)Conquer計(jì)算出新的含本結(jié)點(diǎn)cur_max(上一層不能有相鄰的，只能用left/right.prev)和prev_max(沒相鄰orNot限制，選前面最大的就行）
Time Complexity: O(N) Space Complexity: O(1)
Solution Code：
class Solution {
class Result {
int cur_max;
int prev_max;
Result(int cur_max, int prev_max) {
this.cur_max = cur_max;
this.prev_max = prev_max;
}
}
public int rob(TreeNode root) {
Result result = dfsHelper(root);
return Math.max(result.cur_max, result.prev_max);
}
private Result dfsHelper(TreeNode node) {
if(node == null) return new Result(0, 0);
Result left = dfsHelper(node.left);
Result right = dfsHelper(node.right);
// consider this one
int cur_max = left.prev_max + right.prev_max + node.val;
// if including negative case
// int cur_max = Math.max(left.prev_max + right.prev_max, Math.max(left.prev_max, right.prev_max)) + node.val;
// don't consider this one
int prev_max = Math.max(left.cur_max, left.prev_max) + Math.max(right.cur_max, right.prev_max);
Result result = new Result(cur_max, prev_max);
return result;
}
}
