Leetcode 337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

思路：

1. 对于每个node，我们如果选择偷，则最大值等于node.val和它的孙子层的所有节点最大值的和；如果不偷，最大值等于它的左右儿子节点的最大值之和。
2. 由于从root开始向下搜索，越靠近底部的节点被重复计算的次数越多，因此可以用一个hashmap来记录底层已经计算过的节点，这样每个节点只会被计算一次。

public class HouseRobberIII {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Map<TreeNode, Integer> map = new HashMap<>();
        return robHelper(root, map);
    }

    private int robHelper(TreeNode root, Map<TreeNode, Integer> map) {
        if (root == null) {
            return 0;
        }
        if (map.containsKey(root)) {
            return map.get(root);
        }

        int res = root.val;
        if (root.left != null) {
            res += robHelper(root.left.left, map) + robHelper(root.left.right, map);
        }
        if (root.right != null) {
            res += robHelper(root.right.left, map) + robHelper(root.right.right, map);
        }
        int val = Math.max(res, robHelper(root.left, map) + robHelper(root.right, map));
        map.put(root, val);
        return val;
    }
}