- 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.
思路:
对于每个 node, 我们如果选择偷, 则最大值等于 node.val 和它的孙子层的所有节点最大值的和; 如果不偷, 最大值等于它的左右儿子节点的最大值之和
由于从 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;
- }
- }
来源: http://www.jianshu.com/p/241b6c424a43