这题看上去不是很难，我按照我的理解，用动态规划的思想，写下了如下的代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
unordered_map<TreeNode*, int> memo;
public:
int money(TreeNode* root){
if(root==nullptr)
return 0;
if(memo.find(root)!=memo.end())
return memo[root];
int coins=0;
if(root->left==nullptr&&root->right==nullptr)
coins=root->val;
else if(root->left==nullptr)
coins=root->val+money(root->right->left)
+money(root->right->right);
else if(root->right==nullptr)
coins=root->val+money(root->left->left)
+money(root->left->right);
else
coins=root->val+money(root->left->left)
+money(root->left->right)+money(root->right->left)
+money(root->right->right);
memo[root]=coins;
return coins;
}
int rob(TreeNode* root) {
return max(money(root),money(root->left)+money(root->right));
}
};
我将money(root)定义为一定偷root钱的情况下达到的最大偷盗金额，用memo记录数值防止重复计算。对于某一个结点， 按照它的子结点是否存在进行分类讨论，当左右结点都存在的时候它的最大值应该是它本身加上隔层的所有结点最大值。当我提交后， 我才意识到我的做法根本不对，我的报错例子如下：
我的代码结果是6，实际结果应该是7，过了很久我都没有意识到6的错误在哪，直到我发现4+3=7。也就是说最大值不一定是money(root)+money(root->left->left)+money(root->left->right)+money(root->right->left)+money(root->right->right)。我们没办法确定隔层的结点全部偷是最好的做法，所以这样定dp是行不通的。
我们再更改dp的定义，定义表示最大偷盗金额，但不一定会偷root本身，基本只需要改一行代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
unordered_map<TreeNode*, int> memo;
public:
int money(TreeNode* root){
if(root==nullptr)
return 0;
if(memo.find(root)!=memo.end())
return memo[root];
int coins=0;
if(root->left==nullptr&&root->right==nullptr)
coins=root->val;
else if(root->left==nullptr)
coins=root->val+money(root->right->left)
+money(root->right->right);
else if(root->right==nullptr)
coins=root->val+money(root->left->left)
+money(root->left->right);
else
coins=root->val+money(root->left->left)
+money(root->left->right)+money(root->right->left)
+money(root->right->right);
//memo[root]=coins;
memo[root]=max(coins,money(root->left)+money(root->right));
return memo[root];
}
int rob(TreeNode* root) {
return max(money(root),money(root->left)+money(root->right));
}
};
文档信息
- 本文作者：weownthenight
- 本文链接：https://weownthenight.github.io/2022/05/05/leetcode%E9%A2%98%E8%A7%A3-%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）