leecode337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
 

提示：

树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104

利用记忆化搜索

class Solution {
    public int rob(TreeNode root) {
        Map<Cache, Integer> map = new HashMap<>();
        return Math.max(root.val + dfs(root.left, true, map) + dfs(root.right, true, map), dfs(root.left, false, map) + dfs(root.right, false, map));
    }

    public int dfs(TreeNode node, boolean parentSelect, Map<Cache, Integer> map) {
        if (node == null) {
            return 0;
        }
        Cache cache = new Cache(node, parentSelect);
        if (parentSelect) {//父节点选了，下面两个都不能选了
            if (!map.containsKey(cache)) {
                map.put(cache, dfs(node.left, false, map) + dfs(node.right, false, map));
            }

        } else {
            if (!map.containsKey(cache)) {
                //选此节点
                int cnt = node.val + dfs(node.left, true, map) + dfs(node.right, true, map);
                //不选此节点
                int cnt1 = dfs(node.left, false, map) + dfs(node.right, false, map);
                map.put(cache, Math.max(cnt1, cnt));
            }
        }
        return map.get(cache);
    }


    class Cache {
        TreeNode node;
        boolean parentSelect;

        public Cache(TreeNode node, boolean parentSelect) {
            this.node = node;
            this.parentSelect = parentSelect;
        }

        public TreeNode getNode() {
            return node;
        }

        public void setNode(TreeNode node) {
            this.node = node;
        }

        public boolean isParentSelect() {
            return parentSelect;
        }

        public void setParentSelect(boolean parentSelect) {
            this.parentSelect = parentSelect;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Cache)) return false;
            Cache cache = (Cache) o;
            return parentSelect == cache.parentSelect && Objects.equals(node, cache.node);
        }

        @Override
        public int hashCode() {
            return Objects.hash(node, parentSelect);
        }
    }
}