# Two easy understanding recursive solutions with HashMap memory

• Solution1:

``````Map<TreeNode, Integer> Optimalmap; //Store the optimal result for each root
Map<TreeNode, Integer> NonRobmap;//Store the optimal result for each root, if we don't rob it
public int rob(TreeNode root) {
this.Optimalmap = new HashMap<TreeNode, Integer>();
this.NonRobmap = new HashMap<TreeNode, Integer>();
return robHelper(root,true);
}
public int robHelper(TreeNode root, boolean canRob) {
int result = 0;
if(root!=null){
if(canRob) {//if root can be robbed, we can rob it or not, and there exists an optimal choice
if(Optimalmap.containsKey(root)) return Optimalmap.get(root);
//We can rob it
int RobIt = root.val+robHelper(root.left,false)+robHelper(root.right,false);
if(!NonRobmap.containsKey(root)) //We don't rob it
NonRobmap.put(root,robHelper(root.left,true)+robHelper(root.right,true));
int notRobIt = NonRobmap.get(root);
result = Math.max(RobIt,notRobIt); //Optimal result is the maximum of (RobIt,notRobIt)
Optimalmap.put(root,result);
}
else {//if root can't be robbed
if(NonRobmap.containsKey(root)) return NonRobmap.get(root);
result = robHelper(root.left,true)+robHelper(root.right,true);
NonRobmap.put(root,result);
}
}
return result;
}
``````

Solution2:

``````Map<TreeNode, Integer> Robmap;//Store the optimal result for each root, if we rob it
Map<TreeNode, Integer> NonRobmap;//Store the optimal result for each root, if we don't rob it
public int rob(TreeNode root) {
this.Robmap = new HashMap<TreeNode, Integer>();
this.NonRobmap = new HashMap<TreeNode, Integer>();
return robHelper(root,true);
}
public int robHelper(TreeNode root, boolean canRob) {
int result = 0;
if(root!=null){
if(canRob) {//if root can be robbed, we can rob it or not
if(!Robmap.containsKey(root)) //We can rob it
Robmap.put(root,root.val+robHelper(root.left,false)+robHelper(root.right,false));
int RobIt = Robmap.get(root);
if(!NonRobmap.containsKey(root)) //We can not rob it
NonRobmap.put(root,robHelper(root.left,true)+robHelper(root.right,true));
int notRobIt = NonRobmap.get(root);
result = Math.max(RobIt,notRobIt); //Optimal result is the maximum of (RobIt,notRobIt)
}
else {//if root can't be robbed, we
if(NonRobmap.containsKey(root)) return NonRobmap.get(root);
result = robHelper(root.left,true)+robHelper(root.right,true);
NonRobmap.put(root,result);
}
}
return result;
}``````

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