House Robber III — Leetcode 337

Original problem link: https://leetcode.com/problems/house-robber-iii/

In this problem, we’re given a binary tree representing houses to rob with some amount of money in each of them and we want to find the max profit the robber can get without alerting the police (e.g. not robbing two linked houses).

/**
 * 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 {
    
    Map<TreeNode, Integer> cacheRob;
    
    public int rob(TreeNode root) {
        cacheRob = new HashMap<>();
        return findMax(root, true);
    }
    
    public int findMax(TreeNode node, boolean canInclude) {
        if (node == null) {
            return 0;
        }
        if (canInclude && cacheRob.containsKey(node)) {
            return cacheRob.get(node);
        }
        
        if (canInclude) {
            int result = Math.max(node.val + findMax(node.left, !canInclude) + findMax(node.right, !canInclude), findMax(node.left, canInclude) + findMax(node.right, canInclude));
            cacheRob.put(node, result);
            return result;
        } else {
            return findMax(node.left, !canInclude) + findMax(node.right, !canInclude);
        }
    }
}

My solution uses recursive and whether to include a house or exclude it and takes the max of both paths when possible. It uses a cache to reduce the runtime to 2–5 ms.