Description
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
Idea
Use recursion with cache. If the root is chose, then you have to recurse on grandchildren. If it's not, then you recurse on children.
Solution
class Solution {
private:
int robHelper(TreeNode *root, unordered_map<TreeNode*, int> &cache) {
if (cache.find(root) != cache.end()) return cache[root];
else if (!root) return 0;
else {
int choose = root->val, not_choose = 0;
if (root->left) not_choose += robHelper(root->left, cache);
if (root->right) not_choose += robHelper(root->right, cache);
if (root->left && root->left->left) choose += robHelper(root->left->left, cache);
if (root->left && root->left->right) choose += robHelper(root->left->right, cache);
if (root->right && root->right->left) choose += robHelper(root->right->left, cache);
if (root->right && root->right->right) choose += robHelper(root->right->right, cache);
int rtn = max(choose, not_choose);
cache[root] = rtn;
return rtn;
}
}
public:
int rob(TreeNode* root) {
unordered_map<TreeNode*, int> cache;
return robHelper(root, cache);
}
};
124 / 124 test cases passed.
Runtime: 15 ms
