当前位置：网站首页>leetcode：337. 打家劫舍 III

leetcode：337. 打家劫舍 III

2022-08-10 16:39:00 【OceanStar的学习笔记】

题目来源

leetcode：337. 打家劫舍 III

题目描述

在这里插入图片描述

struct TreeNode {
    
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {
    }
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {
    }
};

class Solution {
    
public:
    int rob(TreeNode* root) {
    

    }
};

题目解析

对于每一个node，它有两种决策：

偷当前节点，那么它的左右子树均不能偷
不偷当前节点，那么它的左右子树可以偷也可以不偷

因此，每次都需要从左树和右树中我们都需要偷，不偷的最大收益

class Solution {
    
    struct Info{
    
        int yes;
        int no;
        
        Info(int y, int n) : yes(y), no(n){
    
        }
    };
    
    Info * process(TreeNode* root){
    
        if(root == nullptr){
    
            return new Info(0, 0);
        }
        
        auto left = process(root->left);
        auto right = process(root->right);
        int yes = 0, no = 0;
        yes = root->val + left->no + right->no;  // 偷当前节点，那么子节点均不能偷
        no =  std::max(left->yes, left->no) + std::max(right->yes, right->no);  // 不偷当前节点，那么子节点可偷可不偷
        return new Info(yes, no);
    }
public:
    int rob(TreeNode* root) {
    
        auto item = process(root);
        return std::max(item->yes, item->no);
    }
};