# My Java Solution (DP +DFS) using hashmap, easy to understand

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
private HashMap<TreeNode,Integer> taken;
private HashMap<TreeNode,Integer> notTaken;
public int rob(TreeNode root) {
taken = new HashMap<>();
notTaken = new HashMap<>();
if(root == null){
return 0;
}
helper(root);
return Math.max(taken.get(root),notTaken.get(root));
}

public void helper(TreeNode node){
// System.out.println(node.val + " vvv ");

int currTaken = node.val, currNotTaken = 0, a = 0, b = 0;
if(node.left == null && node.right == null){
taken.put(node,node.val);
notTaken.put(node,0);
return;
}
if(node.left != null){
helper(node.left);
a = taken.get(node.left);
b = notTaken.get(node.left);
currNotTaken += Math.max(a,b);
currTaken += b;
}
if(node.right != null){
helper(node.right);
a = taken.get(node.right);
b = notTaken.get(node.right);
currNotTaken += Math.max(a,b);
currTaken += b;
}
// System.out.println(node.val + " vvv ");
// System.out.println(currNotTaken + " notttt ttt " + (currTaken));
notTaken.put(node,currNotTaken);
taken.put(node,currTaken);
return;
}
}
``````

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