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.

Example

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Maximum amount of money the thief can rob = 4 + 5 = 9.

这题一开始用递归结果超时；随机加cache变成DP。。通过了

helper1表示抢root

helper2表示不抢root；此处注意不抢root时即可以抢root.left和root.right 也可以不抢它们二取其一所以注意42-47行

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     /**
11      * @param root: The root of binary tree.
12      * @return: The maximum amount of money you can rob tonight
13      */
14      Map<TreeNode, Integer> map1 = new HashMap<TreeNode, Integer>();
15      Map<TreeNode, Integer> map2 = new HashMap<TreeNode, Integer>();
16     public int houseRobber3(TreeNode root) {
17         // write your code here
18         if(root==null) return 0;
19         return Math.max(helper1(root), helper2(root));
20     }
21     // include root
22     private int helper1(TreeNode root){
23         if(map1.containsKey(root)){
24             return map1.get(root);
25         }
26         int sum = root.val;
27         if(root.left!=null){
28             sum += helper2(root.left);
29         }
30         if(root.right!=null){
31             sum += helper2(root.right);
32         }
33         map1.put(root, sum);
34         return sum;
35     }
36     // not include root
37     private int helper2(TreeNode root){
38         if(map2.containsKey(root)){
39             return map2.get(root);
40         }
41         int sum = 0;
42         if(root.left!=null){
43             sum += Math.max(helper1(root.left), helper2(root.left));
44         }
45         if(root.right!=null){
46             sum += Math.max(helper1(root.right), helper2(root.right));
47         }
48         map2.put(root, sum);
49         return sum;
50     }
51 }