Leetcode 337. 打家劫舍 III（DAY 88) ---- Leetcode Hot 100

原题题目

代码实现（首刷自解 之前没做明白 说明3个月的提升aaa）

/*** Definition for a binary tree node.* 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:unordered_map<TreeNode*,int> m;int rob(TreeNode* root) {
    if(!root)   return 0;int l = rob(root->left);int r = rob(root->right);int ll = 0,lr = 0,rl = 0,rr = 0;if(root->left){
    ll = m[root->left->left];lr = m[root->left->right];}  if(root->right){
    rl = m[root->right->left];rr = m[root->right->right];}if(l + r >= ll + lr + rl + rr + root->val)m[root] = l + r;else   m[root] = ll + lr + rl + rr + root->val;return m[root];}
};

代码实现（二刷思路想出来了 map优化看的原来的 DAY 229 C++）

/*** Definition for a binary tree node.* 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:unordered_map<TreeNode*,int> map;int solution_rob(TreeNode* root){
    if(!root)   return 0;int l = solution_rob(root->left);int r = solution_rob(root->right);   int ll = (root->left ? map[root->left->left] : 0);int lr = (root->left ? map[root->left->right] : 0);int rl = (root->right ? map[root->right->left] : 0);int rr = (root->right ? map[root->right->right] : 0);int ret_max = max(root->val + ll + lr + rl + rr,l + r);map[root] = ret_max; return ret_max;}int rob(TreeNode* root) {
    return solution_rob(root); }
};

代码实现（三刷自解 DAY 322 C++）

/*** Definition for a binary tree node.* 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:unordered_map<TreeNode*, int> map;int Helper(int& ans, TreeNode* root) {
    if (!root) {
    return 0;}int sum = 0;int left = Helper(ans, root->left);int right = Helper(ans, root->right);int ll = 0, lr = 0, rl = 0, rr = 0;if (root->left) {
    ll = map[root->left->left];lr = map[root->left->right];}if (root->right) {
    rl = map[root->right->left];rr = map[root->right->right];}sum = max(sum, max(root->val + ll + lr + rl + rr, left + right));map[root] = sum;ans = max(ans, sum);return sum;}int rob(TreeNode* root) {
    map[nullptr] = 0;int ans = 0;Helper(ans, root);return ans;}
};