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和它的孫子層的所有節(jié)點最大值的和；如果不偷，最大值等于它的左右兒子節(jié)點的最大值之和。
2. 由于從root開始向下搜索，越靠近底部的節(jié)點被重復計算的次數(shù)越多，因此可以用一個hashmap來記錄底層已經(jīng)計算過的節(jié)點，這樣每個節(jié)點只會被計算一次。

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