House Robber III

House Robber III

Description:

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:

 3
/  
2    3
 \     \
 3      1

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

 3
/ 
4     5
/ \     \
1   3    1

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

分析：

Code：

DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: The maximum amount of money you can rob tonight
     */
    int houseRobber3(TreeNode* root) {
        // write your code here
        unordered_map<TreeNode*, int> m;
        
        return dfs(root, m);
    }
    
    int dfs(TreeNode *root, unordered_map<TreeNode*, int> &m) {
        if (root == nullptr) return 0;
        if (m.count(root)) return m[root];
        
        int val = 0;
        if (root->left) {
            val += dfs(root->left->left, m) + dfs(root->left->right, m);
        }
        if (root->right) {
            val += dfs(root->right->left, m) + dfs(root->right->right, m);
        }
        val = max(val + root->val, dfs(root->left, m) + dfs(root->right, m));
        m[root] = val;
        
        return val;
    }
};

DP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: The maximum amount of money you can rob tonight
     */
    int houseRobber3(TreeNode* root) {
        // write your code here
        vector<int> ans = dp(root);
        return max(ans[0], ans[1]);
    }
    
    vector<int> dp(TreeNode* root) {
        if (root == nullptr) {
            vector<int> now{0, 0};
            return now;
        }

        vector<int> left = dp(root->left);
        vector<int> right = dp(root->right);
        vector<int> now(2, 0);
        now[0] = max(left[0], left[1]) + max(right[0], right[1]);
        now[1] = left[0] + right[0] + root->val;
        return now;
    }
};