文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
House Robber III
2. Solution
- Version 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) {
return 0;
}
int sum = 0;
if(root->left) {
sum = sum + rob(root->left->left) + rob(root->left->right);
}
if(root->right) {
sum = sum + rob(root->right->left) + rob(root->right->right);
}
return max(root->val + sum, rob(root->left) + rob(root->right));
}
};
- Version 2
/**
* 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) {
unordered_map<TreeNode*, int> m;
return rob(root, m);
}
private:
int rob(TreeNode* root, unordered_map<TreeNode*, int>& m) {
if(!root) {
return 0;
}
if(m.find(root) != m.end()) {
return m[root];
}
int sum = 0;
if(root->left) {
sum = sum + rob(root->left->left, m) + rob(root->left->right, m);
}
if(root->right) {
sum = sum + rob(root->right->left, m) + rob(root->right->right, m);
}
m[root] = max(root->val + sum, rob(root->left, m) + rob(root->right, m));
return m[root];
}
};
