解题思路
class Solution {
Map<TreeNode, Integer> memo = new HashMap<>();
public int rob(TreeNode root) {
return helper(root);
}
public int helper(TreeNode root){
if(root == null)
return 0;
if(memo.containsKey(root))
return memo.get(root);
// t1代表对当前root行窃,行窃后就不能够对其相邻的左右孩子动手
// 因此,直接跳过其左右孩子
int t1 = root.val;
if(root.left != null)
t1 += helper(root.left.left) + helper(root.left.right);
if(root.right != null)
t1 += helper(root.right.left) + helper(root.right.right);
// t2表示不对当前root行窃
int t2 = 0;
t2 += helper(root.left) + helper(root.right);
// 取最大值,并记忆
t1 = Math.max(t1, t2);
memo.put(root, t1);
return t1;
}
}
解题思路
a[0]=root.val+left[1]+right[1]
,对root行窃,那么对其相邻的左右孩子只能不行窃a[1]=max(left[0],left[1])+max(right[0],right[1])
,对root不行窃,对其左右孩子可偷可不偷,选择偷或不偷的最大值class Solution {
public int rob(TreeNode root) {
int[] ans = helper(root);
return Math.max(ans[0], ans[1]);
}
public int[] helper(TreeNode root){
if(root == null)
return new int[]{0, 0};
int[] left = helper(root.left);
int[] right = helper(root.right);
return new int[]{root.val + left[1] + right[1],
Math.max(left[0], left[1]) + Math.max(right[0], right[1])};
}
}