打家劫舍3

---

• 总结：基本上都要两个数据结构，一个记录选，一个记录不选。无后效性只需要管好当前几个就行。

使用map<TreeNode*,int>替代数组作为离散数值容器（还有个好处是null不存在map[null]自动返回0），index-2/-3改成->left->left,->right->left...

• 使用后序遍历保证两个子节点的解先解出来。

• 当root点被选中的时候，左右两个次root点一定不被选中，为nothas(root->left)+nothas(root->right)

• 当root点未被选中的时候，左右两个点可以选中也可以不选中，所以max(has(root->left),nothas(root->left))+max(has(root->left)+nothas(root->right))即可

• 不再是max(a,b)而是max(a+b)的关系

image.png

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/**
 * 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>nothas;
    map<TreeNode*,int>has;
    void Rob(TreeNode* root){
        if(root==NULL){
            return;
        }
        Rob(root->left);
        Rob(root->right);        
        // choose
        has[root]=nothas[root->left]+nothas[root->right]+root->val;
        // not choose
        nothas[root]=max(has[root->left],nothas[root->left])+max(has[root->right],nothas[root->right]);
    }
    int rob(TreeNode* root) {
        Rob(root);
        return max(has[root],nothas[root]);
    }
};