# concise, easy, clear JAVA solution

• '''

public int rob(TreeNode root) {
return dfs(root, false);
}

int dfs(TreeNode t, boolean isParentRobed){
if (t == null) return 0;

//rob t
int a1 = 0;
if (!isParentRobed) a1 = t.val + dfs(t.left, true) + dfs(t.right, true);

//not rob t
int a2 = dfs(t.left, false) + dfs(t.right, false);

return Math.max(a1, a2);

}

''''

• Here comes the DP version.

'''

public int rob(TreeNode root) {
Map<TreeNode, Integer>[] maps = new Map[2];
for (int i=0; i<2; i++) maps[i] = new HashMap<>();

return dfs(root, false, maps);
}

int dfs(TreeNode t, boolean isParentRobed, Map<TreeNode, Integer>[] maps){
if (t == null) return 0;

int idx = isParentRobed?1:0;
if (!maps[idx].containsKey(t)){

//rob t
int a1 = 0;
if (!isParentRobed) a1 = t.val + dfs(t.left, true, maps) + dfs(t.right, true, maps);

//not rob t
int a2 = dfs(t.left, false, maps) + dfs(t.right, false, maps);

maps[idx].put(t, Math.max(a1, a2));
}

return maps[idx].get(t);
}

''';

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.