[数据结构与算法]leetcode 337 打家劫舍III

前言

题目：337. 打家劫舍 III

参考题解：打家劫舍 III-力扣官方题解

提交代码

二叉树的题目。考虑的时候，需要递归思考。即把树拆分成根，左子树，右子树。

这样思考之后，题目很容易有思路。思路见代码实现。

本题需要使用附加空间存储信息。否则，会超时。

另外，不要用脑袋瓜子去思考下面代码中的递归过程。按照只直觉的逻辑思路码代码就成。

class Solution {
private:
    unordered_map<TreeNode*,int> record;
public:
    int rob(TreeNode* root) {
        if(record[root])
            return record[root];
        if(root == nullptr)
            return 0;
        
        int steal_root = root->val;
        if(root->left) 
            steal_root = steal_root + rob(root->left->left) + rob(root->left->right);
        if(root->right)
            steal_root = steal_root + rob(root->right->left) + rob(root->right->right);
        
        int not_steal_root = rob(root->left) + rob(root->right);

        record[root] = max(steal_root,not_steal_root);
        return record[root];
    }
};