政子的博客

技术|学习|随笔

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