LeetCode-House Robber III

直接使用递归的方式,算法超时。不过发现有重复的子问题,应该有优化的空间。

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
return max(helper(root,true),helper(root,false));
}
int helper(TreeNode* root, bool isRobbed){
if(root==nullptr) return 0;
int money=0;
if(isRobbed) money=helper(root->left,false)+helper(root->right,false);
else money=max(
helper(root->left,true)+helper(root->right,true)+root->val,
helper(root->left,false)+helper(root->right,false)
);
return money;
}
};

其实没必要分这么多情况,可以将递归写在一个函数中,但依旧超时,无法通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
unordered_map<TreeNode*,int> dp;
public:
int rob(TreeNode* root) {
if(root==nullptr) return 0;
int money1=rob(root->left)+rob(root->right);
int money2=root->val;
if(root->left) money2+=rob(root->left->left)+rob(root->left->right);
if(root->right) money2+=rob(root->right->left)+rob(root->right->right);
int money=max(money1,money2);
return money;
}
};

优化的方法就是使用空间换时间,将最优的解法使用哈希表记录下来,需要的时候直接查询。

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
unordered_map<TreeNode*,int> dp;
public:
int rob(TreeNode* root) {
if(root==nullptr) return 0;
auto res=dp.find(root);
if(res!=dp.end()) return res->second;
int money1=rob(root->left)+rob(root->right);
int money2=root->val;
if(root->left) money2+=rob(root->left->left)+rob(root->left->right);
if(root->right) money2+=rob(root->right->left)+rob(root->right->right);
int money=max(money1,money2);
dp.insert(pair<TreeNode*,int>(root,money));
return money;
}
};

在讨论区找到了更厉害的解法,把递归中需要的参数变成了引用,直接传出。必须要好好学习一下这种解法,它无疑在空间和时间上都很占优势。

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int tryRob(TreeNode* root, int& l, int& r) {
if (!root)
return 0;

int ll = 0, lr = 0, rl = 0, rr = 0;
l = tryRob(root->left, ll, lr);
r = tryRob(root->right, rl, rr);

return max(root->val + ll + lr + rl + rr, l + r);
}

int rob(TreeNode* root) {
int l, r;
return tryRob(root, l, r);
}
};