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:

     3
    / \
   2   3
    \   \ 
     3   1

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

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

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

/**
 * 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:
    map<TreeNode*, int> mt;
    map<TreeNode*, int> mf;
    
    inline int max(int a, int b){
        return a > b ? a : b;
    }
    inline int max4(int a, int b, int c, int d){
        int m = a;
        if(m < b) m = b;
        if(m < c) m = c;
        if(m < d) m = d;
        return m;
    }
    int fun(TreeNode* root, bool coin){
        if(NULL == root) return 0;
        
        if(coin){
            if(mt.count(root) > 0) return mt[root];
            int v = fun(root->left, false) + fun(root->right, false) + root->val;
            mt[root] = v;
            return v;
        }else{
            if(mf.count(root) > 0) return mf[root];
            
            int v = max4(
                fun(root->left, true) + fun(root->right, true), 
                fun(root->left, true) + fun(root->right, false),
                fun(root->left, false) + fun(root->right, true),
                fun(root->left, false) + fun(root->right, false)
            );
            mf[root] = v;
            return v;
        }
    }
    int rob(TreeNode* root) {
        if(NULL == root) return 0;
        return max(fun(root, true), fun(root, false));      
    }
};

Solution2:

/**
 * 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:
    map<TreeNode*, int> mt;
    map<TreeNode*, int> mf;
    
    inline int max(int a, int b){
        return a > b ? a : b;
    }
    
    int dfs(TreeNode* root){
        if(NULL == root) return 0;
        if(mt.count(root) > 0) return mt[root];
        int val = 0;
        if(root->left) val += dfs(root->left->left) + dfs(root->left->right);
        if(root->right) val += dfs(root->right->left) + dfs(root->right->right);
        val = max(root->val + val, dfs(root->left) + dfs(root->right));
        mt[root] = val;
        return val;
    }
    
    int rob(TreeNode* root) {
        if(NULL == root) return 0;
        return dfs(root);    
    }
};