House robber III

Problem

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) ;
    }
}