LeetCode 337 打家劫舍III

打家劫舍III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

给定二叉树的 root 。返回在不触动警报的情况下，小偷能够盗取的最高金额。

示例：

输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

深度优先

改变了相邻节点的定义：此处是在一棵二叉树中进行节点的选取，使得节点的和值最大，那么从父节点开始遍历，选取了父节点就不能选取子节点。

暴力搜索实现：遍历每一种合法的选取情形，判断能够选取到的最大值。

代码实现：

class Solution {
public:
    int robTree(TreeNode* root){ // 计算对于以root为根节点能够抢到的最大的值
        if(root){ // 当前节点非空
            if(!root->left&&!root->right) return root->val;
            int val1=root->val;
            if(root->left) val1+=(robTree(root->left->left)+robTree(root->left->right));
            if(root->right) val1+=(robTree(root->right->left)+robTree(root->right->right));
            int val2=robTree(root->left)+robTree(root->right);
            return max(val1,val2);
        }
        return 0;
    }
    int rob(TreeNode* root) {
        return robTree(root);
    }
};

这样的实现方式，本质上是在进行穷举，不断尝试选取方案，类似于是回溯的方法实现，在LeetCode的测试用例中将会超出时间限制。

记忆化搜索：在上述的计算过程中存在较多的重复计算。比如在计算 robTree(root->left) 的时候就重复计算了 (robTree(root->left->left)+robTree(root->left->right)) ，使用一个map记录计算的过程，从而减少计算。此处在基于记忆化搜索时，有一个非常需要注意的点：使用一个Map进行记录，那么对于正在寻找最大值的当前节点，在开始遍历前，尝试访问map中的数据，若是访问成功，那么本次求解直接结束（在非空和非叶子节点的情形下），若是访问失败，那么按照正常的遍历方式去进行DFS，在本次访问返回前将相应的数值存储在map中。

class Solution {
public:
    unordered_map<TreeNode* , int> umap; // 记录计算过的结果
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return root->val;
        if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回
        // 偷父节点
        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right
        // 不偷父节点
        int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
        umap[root] = max(val1, val2); // umap记录一下结果
        return max(val1, val2);
    }
};

动态规划

此处的动态规划实现，基本上和记忆化搜索类似。也是在递归的基础上实现。进行动态规划的基本思路依旧是：对于以 root 为根的子树，能够选取到的最大的节点数值总和为，max(选取当前节点+两棵子树后代的最大值，不选当前节点两棵子树的最大值之和) 。

此处需要基于动态规划实现，并且要避免重复的计算操作，那么使用一个递归函数，返回一个长度为2的数组，分别记录：选取根节点能够获取的最大值，不选取根节点能够获取到的最大值。

动态规划数组的定义：对于递归函数 robTree(TreeNode* root)，返回 vector<int> dp(2) ，分别记录：选取根节点能够获取的最大值，不选取根节点能够获取到的最大值。
动态规划数组的推导：在当前的递归函数层中，需要计算的有两个值，其中 dp[0] 表示的是选取根节点能够获取到的最大值，那么左右孩子节点是一定不能够选取的 dp[0]=root->val+robTree(root->left)[1]+robTree(root->right)[1] ，对于dp[1] 表示的是不选取根节点能够获取到的最大值，此时左右孩子节点是可选可不选的，那么具体能否进行选取，取决那种方式能够获取到更大的值 dp[1]=max(robTree(root->left)[0],robTree(root->left)[1])+max(robTree(root->right)[0],robTree(root->right)[1])
动态规划数组的初始化：对于空节点 robTree(nullptr)={0,0}
动态规划数组的遍历顺序：本质上就是DFS，并且对于根节点而言是后序遍历

代码实现：

class Solution {
public:
    vector<int> robTree(TreeNode* root){
        if(root){
            vector<int> val1=robTree(root->left);
            vector<int> val2=robTree(root->right);
            vector<int> res(2);
            res[0]=root->val+val1[1]+val2[1];
            res[1]=max(val1[0],val1[1])+max(val2[0],val2[1]);
            return res;
        }
        return {0,0};
    }
    int rob(TreeNode* root) {
       vector<int> res=robTree(root);
       return max(res[0],res[1]);
    }
};

在动态规划的过程中，采取的是后序遍历的方式，上层节点的值是在底层节点的值完成计算后，才得到的，并且使用一个vector数组同时记录了选取根节点和不选取根节点的最优解。但是由于在递归函数的返回值中使用的是vector数组，vector数组在创建时将会预分配较大的内存空间，导致程序的开销较大，此处改用 pair ，将会使得LeetCode上的运行时间和内存空间大大降低。

class Solution {
public:
    pair<int,int> robTree(TreeNode* root){
        if(root){
            pair<int,int> val1=robTree(root->left);
            pair<int,int> val2=robTree(root->right);
            pair<int,int> res;
            res.first=root->val+val1.second+val2.second;
            res.second=max(val1.first,val1.second)+max(val2.first,val2.second);
            return res;
        }
        return {0,0};
    }
    int rob(TreeNode* root) {
       pair<int,int> res=robTree(root);
       return max(res.first,res.second);
    }
};

Mark's blogs

LeetCode-337-打家劫舍III

LeetCode 337 打家劫舍III

深度优先

动态规划