题目描述
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例：
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
题目链接： https://leetcode-cn.com/problems/house-robber-iii/
思路1
因为不能打劫两个直接相连的房子，所以对于一个3层的树来说，有两种打劫的方法：
- 打劫爷爷节点+打劫孙子节点：root->val+rub(root->left->left)+rub(root->left->right)+rub(root->right->left)+rub(root->right->right);
- 打劫父亲节点：rub(root->left)+rub(root->right);
取两种方法的最大值即可。这种方法可以使用递归实现，代码如下：
/**
* 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) {
if(root==nullptr) return 0;
int money = root->val;
if(root->left!=nullptr){
money += (rob(root->left->left) + rob(root->left->right));
}
if(root->right!=nullptr){
money += (rob(root->right->left) + rob(root->right->right));
}
return max(money, rob(root->left)+rob(root->right));
}
};
- 时间复杂度：O(2^N)
- 空间复杂度：O(h)
该方法由于时间复杂度过高未通过。
思路2
思路1时间复杂度过高的原因是有很多节点被重复计算了。为了避免重复计算，我们可以使用哈希表记录下来从某节点开始能抢劫到的最大钱数，这样在递归的过程中，如果节点在哈希表中出现，则直接返回对应的值，也就是备忘录算法。代码如下：
/**
* 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) {
if(root==nullptr) return 0;
unordered_map<TreeNode*, int> dict;
return doRob(root, dict);
}
int doRob(TreeNode* root, unordered_map<TreeNode*, int>& dict){
if(root==nullptr) return 0;
if(dict.find(root)!=dict.end()) return dict[root];
int money = root->val;
if(root->left!=nullptr){
money += (doRob(root->left->left, dict) + doRob(root->left->right, dict));
}
if(root->right!=nullptr){
money += (doRob(root->right->left, dict) + doRob(root->right->right, dict));
}
int result = max(money, doRob(root->left, dict)+doRob(root->right, dict));
dict[root] = result; // 注意位置
return result;
}
};
思路3
使用动态规划。对于每个节点都有两种选择：抢劫和不抢劫，使用1表示抢劫，使用0表示不抢劫，我们使用一个二维数组int res[2]来表示，则
- 抢劫该节点：rob(root)[1] = root->val+rob(root->left)[0]+rob(root->right)[0]；
- 不抢劫该节点：rob(root)[0] = max(rob(root->left)[0],rob(root->left)[1]) + max(rob(root->right)[0],rob(root->right)[1])；
代码如下：
/**
* 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) {
if(root==nullptr) return 0;
int* money = doRob(root);
return max(money[0], money[1]);
}
int* doRob(TreeNode* root){
if(root==nullptr){
int* t = new int[2];
memset(t, 0, sizeof(t));
return t;
};
int* result = new int[2];
memset(result, 0, sizeof(result));
int* left = doRob(root->left);
int* right = doRob(root->right);
result[0] = max(left[0], left[1]) + max(right[0], right[1]);
result[1] = root->val + left[0] + right[0];
return result;
}
};