LeetCode 337. 【DP】【递归】打家劫舍3
原题链接
中等
作者:
大明湖的鱼
,
2021-01-29 23:35:58
,
所有人可见
,
阅读 310
思路
代码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:
unordered_map<TreeNode* ,int> sums;
int rob(TreeNode* root) {
return tryRob(root);
}
int tryRob(TreeNode* node){
if(node == nullptr) return 0;
if(sums.count(node)) return sums[node];
//偷取该节点
int res1 =0;
if(node->left) res1 += (tryRob(node->left->left)+tryRob(node->left->right));
if(node->right) res1 +=(tryRob(node->right->left) + tryRob(node->right->right));
res1 += node->val;
//不偷取该节点
int res2 = tryRob(node->left) + tryRob(node->right);
sums[node] = max(res1,res2);
return sums[node];
}
};
这个动态规划比较容易理解
/**
* 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:
//f is choose , g not choose
unordered_map<TreeNode* ,int> f,g;
int rob(TreeNode* root) {
dfs(root);
return max(f[root],g[root]);
}
void dfs(TreeNode* root){
if(root == nullptr) return;
dfs(root->left);
dfs(root->right);
f[root] = root->val + g[root->left] + g[root->right];
g[root] = max(g[root->left],f[root->left]) + max(g[root->right],f[root->right]);
}
};