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

1
2
3
4
5
  3
 / \
2   3
 \   \ 
  3   1

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

Example 2:

1
2
3
4
5
    3
   / \
  4   5
 / \   \ 
1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Solution:

198. House Robber 213. House Robber II

This problem change the array to a tree structure but the idea is similar. We use a recursive function to sum up the value that starts from root or from its child(root->left and root->right).

  • Solution1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    /**
     * 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 val= 0;
            
            if(root->right){
                val+= rob(root->right->right)+ rob(root->right->left);
            }
            if(root->left){
                val+= rob(root->left->right)+ rob(root->left->left);
            }
            
            return max(root->val+ val, rob(root->right)+rob(root->left));
        }
        
    };

However, this solution has a bad time complexity. It is because we need to recalculate many things. For example, 

1
2
3
4
5
    6
   / \
  4   5
 / \   \ 
1   3   2

If we start from 6, and we calculate the 1, 3, 2(grandchildren) value 1 time.
However, after we calculate 4, 5, we’ll need to calculate 1, 3, 2 again.
This seems not efficient enough, we can use a map to record the node that we’ve already calculated.

  • Solution 2
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    /**
     * 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> map; //use map to store every treeNode in the tree, so that we won't have to recalculate
        
        int rob(TreeNode* root) {
            return robSub(root);
        }
        
        int robSub(TreeNode* root){
            if(!root) return 0;
            int val= 0;
            if(map.find(root) != map.end()) return map.at(root);
            
            if(root->right){
                val+= robSub(root->right->right)+ robSub(root->right->left);
            }
            if(root->left){
                val+= robSub(root->left->right)+ robSub(root->left->left);
            }
            
            val = max(root->val+ val, robSub(root->right)+robSub(root->left));
            map[root]= val;
            return val;
        }
        
    };

Can we do even better?
The major problem is we need to loop up for those already calculated subproblems.
Actually, for each root, there are two scenarios: it is robbed or is not. rob(root) does not distinguish between these two cases, so “information is lost as the recursion goes deeper and deeper”, which results in repeated subproblems.
If we were able to maintain the information about the two scenarios for each tree root, let’s see how it plays out. Redefine rob(root) as a new function which will return an array of two elements, the first element of which denotes the maximum amount of money that can be robbed if root is not robbed, while the second element signifies the maximum amount of money robbed if it is robbed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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) {
        vector<int> res= robSub(root);
        return max(res[0], res[1]);
    }
    
    vector<int> robSub(TreeNode* root){
        if(!root) return vector<int>(2,0);
        vector<int> res(2, 0); //0: w/o root. 1: w/ root
        
        vector<int> left= robSub(root->left);
        vector<int> right= robSub(root->right);
        // result without root = add left[1](include left->val) and right[1](include right->val)
        // but maximum value could be bypass root->left or root->right
        // example:
        // 4-1-1-3
        res[0]= max(left[0], left[1])+ max(right[0], right[1]); 
        
        res[1]= root->val+left[0]+right[0];
        
        return res;
    }
    
};