dfs(root)返回一个大小为2的数组,ans[0]表示root不被偷的最大值,ans[1]表示root被偷的最大值
/**
* 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[] ans=dfs(root);
return Math.max(ans[0],ans[1]);
}
int[] dfs(TreeNode root){
if(root==null) return new int[2];
int[] left=dfs(root.left);
int[] right=dfs(root.right);
int notRub=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
int rub=root.val+left[0]+right[0];
return new int[]{notRub,rub};
}
}