LeetCode/打家劫舍（动态规划树）

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

1. 记忆化搜索

从上往下递归的过程中，会有很多重复递归，将对应节点值存储起来，减少递归运算
这里使用哈希表对离散结构进行记忆化存储

class Solution {
public:
    unordered_map m;
    int rob(TreeNode* root) {
        if(!root) return 0;
        if(m.count(root)) return m[root];
        int val1 = root->val;
        int val2 = 0;
        val2+=rob(root->left);
        val2+=rob(root->right);

        if(root->left){
        val1+=rob(root->left->right);
        val1+=rob(root->left->left);
        }
        if(root->right){
        val1+=rob(root->right->right);
        val1+=rob(root->right->left);     
        }
        m[root]= max(val1,val2);
        return m[root];

    }
};

2. 树状动态规划

相比记忆化搜索，其每个节点只访问了一次，同时返回两种选择状态下的值
便于一次遍历的情况下完成状态的转移

class Solution {
public:
    int rob(TreeNode* root) {
        vector res(2);
        res = traceback(root);
        return max(res[0],res[1]);
    }
    vector traceback(TreeNode* root){//返回偷与不偷时的最大收益
        vector res(2);
        if(!root) return res;
        vector left(2);
        vector right(2);
        if(root->left)
            left = traceback(root->left);
        if(root->right)
            right =  traceback(root->right);
        res[0] = left[1]+right[1]+root->val;
        res[1] = max(left[0],left[1])+ max(right[0],right[1]);
        return res;
    }
};