【力扣】[力扣热题HOT100] 337.打家劫舍|||

1、题目

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

链接:https://leetcode-cn.com/problems/house-robber-iii/

2、思路解析

1)暴力求解法
首先考虑健壮性的问题,检测当前结点和左右子树是否为空。
其次考虑当前结点被偷,则它的结点的左右子树必定不会被偷,则其孙子子树一定会被偷。
如果当前结点不被偷,则其左右子树一定被偷。
最终返回算出来大的结果

class Solution {
public:
    int rob(TreeNode* root) {
        // 时间复杂度过大
        // 健壮性检测
        if(root == nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr) return root->val;

        // 偷当前的
        int val1 = root->val;
        if(root->left) val1 += rob(root->left->left) + rob(root->left->right);
        if(root->right) val1 += rob(root->right->left) +rob(root->right->right);

        // 不偷当前的
        int val2 = rob(root->left) +rob(root->right); 

        // 返回较大的一个
        return max(val1, val2);
    }
};

2)哈希表提高时间复杂度
利用哈希以该节点被偷的金额数记录下来,下次遇到的情况,则直接返回哈希表中的金额数即可。

class Solution {
public:
    unordered_map<TreeNode*, int> map; // 记录已经遍历过的
    int rob(TreeNode* root) {
        if(root == nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr) return root->val;

        // 偷当前的
        int val1 = root->val;
        if(root->left) val1 += rob(root->left->left) + rob(root->left->right);
        if(root->right) val1 += rob(root->right->left) +rob(root->right->right);
        if(map[root]) return map[root];

        // 不偷当前的
        int val2 = rob(root->left) +rob(root->right); 
        map[root] = max(val1, val2); // 记录的是当前结点算出来的是偷盗的最大金额数

        // 返回较大的一个
        return max(val1, val2); 
};

3)动态规划
用哈希表记录该节点 f 表示被偷,g记录该节点不会被偷
当前结点(o)被偷,则其子节点一定不会被偷,即:f(o) = g(o->left) + g(o->right);
当该节点不被偷,则其子节点一定被偷,即:g(o) = f(o->left) + f(o->right);
我们用哈希表存储f,g函数的值,然后深度优先搜索遍历二叉树,得到每一个结点的 f 和 g,因此根节点的 f 和 g 就是最大的值。

class Solution {
public:
    unordered_map<TreeNode*, int> f, g;

    void dfs(TreeNode* root)
    {
        if(!root)
            return;
        dfs(root->left);
        dfs(root->right);
        f[root] = root->val + g[root->left] + g[root->right];
        g[root] = max(f[root->left], g[root->left]) + max(g[root->right], f[root->right]); 
    }

    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root], g[root]);
    }
};
上一篇:LeetCode 310 - Minimum Height Trees (Medium)


下一篇:【leetcode】337. 打家劫舍 III