0337 - House Robber III

[tejasbirsingh]

Description of the Problem

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 1:

Input: [3,2,3,null,3,null,1]

 3
/ \

2 3
\ \
3 1

Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Code

class Solution {
    unordered_map<TreeNode*, int> dp;
public:
    int rob(TreeNode* root) {
        if(!root) return 0;
        if(dp[root]) return dp[root];
        
        int a1 =rob(root->left) + rob(root->right);  // amount  robber can make excluding parent of node
        int a2 =root->val;                           // amount robber can make including parent and excluding child
        if(root->left){ 
            a2 += rob(root->left->left) + rob(root->left->right);
        }
        if(root->right){
            a2 += rob(root->right->left) + rob(root->right->right);
        }
        return dp[root] =max(a1,a2);
    }
};

Link To The LeetCode Problem

https://leetcode.com/problems/house-robber-iii/

I would Like to contribute the code for this issue. Thanks