19. House Robber III

Link to the problem

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