[数据结构与算法]【力扣】[力扣热题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]);
    }
};