TC: O(n) where n is the no. of nodes in the tree

SC: O(n) for using dp map and O(n) for recursive stack space

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/*
cases for the any give node
//consider
if root.val is considered then we can explore root.left.left , root.left.right , root.right.left and root.right.right
//not consider
if root.val is not considered the we can explore root.left and root.right
return Integer.max(consider, not consider)
*/
public int rob(TreeNode root) {
Map<TreeNode,Integer> dp = new HashMap<>();
return max(root,dp);
}
public int max(TreeNode root,Map<TreeNode,Integer> dp){
if(root ==null )return 0;
if(dp.containsKey(root)) return dp.get(root);
int considerRoot = root.val;
if(root.left!=null){
considerRoot+=max(root.left.left,dp) + max(root.left.right,dp);
}
if(root.right!=null){
considerRoot+=max(root.right.left,dp) + max(root.right.right,dp);
}
int dontConsiderRoot = max(root.left,dp) + max(root.right,dp);
dp.put(root,Integer.max(considerRoot,dontConsiderRoot));
return dp.get(root) ;
}
}
```

## Top comments (0)