打家劫舍(三)

//Maxans：当前结点的最大值(递归结束后也就是根结点最大值，也就是结果)
//若当前结点要偷leftnos,rightnos用来保存 上 上 次偷的左右结点值的状态。还要加root->val
//若当前结点不偷，noselect用来保存 上 次偷了的状态。
//最后Maxans取偷或不偷的最大值。
class Solution {
public:
    void dfs(TreeNode*root,int &Maxans,int &noselect)
    {
        if(!root)return ;
        int leftnos=0,rightnos=0,leftMax=0,rightMax=0;
        dfs(root->left,leftMax,leftnos);
        dfs(root->right,rightMax,rightnos);
        noselect=leftMax+rightMax;
        Maxans=max(leftnos+rightnos+root->val,noselect);
    }
    int rob(TreeNode* root) {
        int Maxans=0,noselect=0;
        dfs(root,Maxans,noselect);
        return Maxans;
    }
};

public int rob (TreeNode root) {
    // 对于每一个当前节点：
    // case 1: 偷，left和right都不能偷
    // case 2: 不偷，left和right都可以偷
    // 返回值，必须包含两种状态，偷和不偷
    Status res = getStatus(root);
    return Math.max(res.rob, res.notRob);
}

private Status getStatus(TreeNode root) {
    if (root == null) {
        return new Status(0, 0);
    }
    Status left = getStatus(root.left);
    Status right = getStatus(root.right);
    int rob = left.notRob + right.notRob + root.val;
    int notRob = Math.max(left.rob, left.notRob) + Math.max(right.rob, right.notRob);
    return new Status(rob, notRob);
}

static class Status {
    int rob;
    int notRob;
    public Status (int rob, int notRob) {
        this.rob = rob;
        this.notRob = notRob;
    }
}

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int rob(TreeNode* root) {
        // write code here
        vector<int> res =robTree(root);
        return max(res[0],res[1]);
        
    }
    //0：不偷 1：偷
    vector<int> robTree(TreeNode *cur){
        if(cur==nullptr)return vector<int>{0,0};
        //后序遍历 就最后汇总到根节点
        vector<int> left =robTree(cur->left);
        vector<int> right =robTree(cur->right);
        //偷cur 就不偷他的左和他的右
        int val1= cur->val+left[0]+right[0];
        //不偷cur 就找它左的最大值或者右的最大值之和
        int val2=max(left[0],left[1])+max(right[0],right[1]);
        return {val2,val1};
    }
};

class Solution {
    unordered_map<TreeNode*, int> cache;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int rob(TreeNode* root) {
        // write code here
        return tryRob(root);
    }
    int tryRob(TreeNode* root){
        if(!root) return 0;
        if(cache.count(root)) return cache[root];
        int res1 = 0;
        if(root->left) res1 += tryRob(root->left->left) + tryRob(root->left->right);
        if(root->right) res1 += tryRob(root->right->left) + tryRob(root->right->right);
        res1 += root->val;
        int res2 = tryRob(root->left) + tryRob(root->right);
        return cache[root] = max(res1,res2);
    }
};

有点尴尬，似乎看错题意了

一个BFS+动态规划，居然也有90%通过率。




/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };*/
class Solution{
    public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int rob(TreeNode* root) {
        // write code here ;m, nhkllllll, ll;plo
        vector<vector<int>>vec;
        queue<TreeNode*>q;
        bfs(root,vec,q);
        vector<int>sumall;
        for(int i =0;i<vec.size();i++)           
        {
            int sum=0;
            for(int j =0;j<vec[i].size();j++)
            {
               sum+=vec[i][j]; 
            }
            sumall.push_back(sum);
            sum=0;
        }
        
        vector<int>dp(sumall.size()+1);
        dp[0]=0;
        dp[1]=sumall[0];
        for(int i=2;i<sumall.size()+1;i++)
        {
            dp[i]=max(dp[i-1],dp[i-2]+sumall[i-1]);
        }
        return dp[sumall.size()];
        
    }
    void bfs(TreeNode * root,vector<vector<int>>&vec,queue<TreeNode*>&q)
    {
        if(root==nullptr)
               return;
        q.push(root);
        vector<int>temp;
        //temp.push_back(q.front()->val);
        while(!q.empty())
        {
            int i =0;
            int n =q.size();
            for(;i<n;i++)
            {
                temp.push_back(q.front()->val);
                if(q.front()->left)
                    q.push(q.front()->left);
                if(q.front()->right)
                    q.push(q.front()->right);
                q.pop();
            }
            vec.push_back(temp);
            temp.clear();
        }
        
        return ;
    }
};