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.
一刷
题解：
方法1：问题可以分解为， 取 root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right) 和rob(root.left) + rob(root.right)的较大值。
由于动态规划的思想，这样明显会重复计算很多子问题。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int rob(TreeNode root) {
if(root == null) return 0;
int val = 0;
if(root.left!=null)
val += rob(root.left.left) + rob(root.left.right);
if(root.right !=null)
val += rob(root.right.left) + rob(root.right.right);
return Math.max(val+root.val, rob(root.left) + rob(root.right));
}
}
方法2：
由于方法1有很多重复计算，于是考虑用map存储中间值
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int rob(TreeNode root) {
return robSub(root, new HashMap<>());
}
private int robSub(TreeNode root, Map<TreeNode, Integer> map){
if(root == null) return 0;
if(map.containsKey(root)) return map.get(root);
int val = 0;
if(root.left!=null){
val+= robSub(root.left.left, map) + robSub(root.left.right, map);
}
if(root.right!=null) val+= robSub(root.right.left, map) + robSub(root.right.right, map);
val = Math.max(root.val + val, robSub(root.left, map)+robSub(root.right, map));
map.put(root, val);
return val;
}
}
方法3：
不需要用map存储这么多中间值，只需要存储res[0]表示决定不偷当前root的值对应的结果，res[1]表示偷。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int rob(TreeNode root) {
int[] res = robSub(root);
return Math.max(res[0], res[1]);
}
private int[] robSub(TreeNode root){
if(root == null) return new int[2];
int[] left = robSub(root.left);
int[] right = robSub(root.right);
int[] res = new int[2];
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
}
二刷， 自底向上（用递归实现），动态规划的思路。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int rob(TreeNode root) {
int [] res = robdual(root);
return Math.max(res[0], res[1]);
}
private int[] robdual(TreeNode root){
int[] res = new int[2];
if(root == null) return res;
if(root.left == null && root.right == null){
res[1] = root.val;
return res;
}
int[] left = robdual(root.left);
int[] right = robdual(root.right);
//not rob root
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = left[0] + right[0] + root.val;
return res;
}
}
三刷
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
if(root == null) return 0;
int[] res = robSub(root);
return Math.max(res[0], res[1]);
}
private int[] robSub(TreeNode root){
if(root == null) return new int[2];
int[] left = robSub(root.left);
int[] right = robSub(root.right);
int[] res = new int[2];
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];//rob the root
return res;
}
}
