Java - Recursive DP with short explanation


  • 1
    A

    Recursive solution with memorization. In the statement is given that we can't use two adjacent nodes. So, we have two variants:

    1. to use current node then jump to children's of children.
    2. to not use current node but use answers from children.
    public class Solution {
        
        HashMap<TreeNode, Integer> memo = new HashMap<TreeNode, Integer>();
        
        public int rob(TreeNode root) {
            if (root==null) return 0;
            return calculate(root);
        }
        
        private int calculate(TreeNode node) {
            if (node==null) return 0;
            
            if (memo.containsKey(node)) return memo.get(node);
            
            int use = node.val;
            if (node.left!=null && node.left.left!=null) use += calculate(node.left.left);
            if (node.left!=null && node.left.right!=null) use += calculate(node.left.right);
            if (node.right!=null && node.right.left!=null) use += calculate(node.right.left);
            if (node.right!=null && node.right.right!=null) use += calculate(node.right.right);
    
            int notUse = calculate(node.left) + calculate(node.right);
            int max = Math.max(notUse, use);
            memo.put(node, max);
            return max;
        }
    }
    
    

Log in to reply
 

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