链接：

337. 打家劫舍 III

题意

有一颗二叉树，不能选取相邻节点（直接相邻），求能选取的最大值

解：

与 打家劫舍1 相比，难点在于二叉树分叉时，需要同步分叉节点的选择，即不能一边使用选择了分叉节点的最大值，另一边用没使用分叉节点的最大值

尝试再解一下 打家劫舍1 ，可以发现，正序DP和逆序DP的结果是一样的，而我们现在面对的是二叉树，逆序DP（从叶节点到该节点的DP结果），可以使用深搜完成DP

那么对于每个节点，我们需要计算出选择它的DP结果和不选择它的DP结果

选择它的逆序DP结果：Root.Val+DP[Left][1]+DP[Right][1]，由于自身被选中了，所以子节点均不能选择，再加上自身值即可

那么如何计算DP[?][1]？ state=1表示父节点是选中的，所以返回一个它的DP[Left][2]+DP[Right][2]

同理，计算DP[?][2]，state=2表示父节点是未选中的，这时候子节点选不选都行，则返回它的max( Root.Val+DP[Left][1]+DP[Right][1] , DP[Left][2]+DP[Right][2] )

所以不选择它的逆序DP结果：max( Root.Val+DP[Left][1]+DP[Right][1] , DP[Left][2]+DP[Right][2] )

问题代码：

第一个是AC代码，但是可以发现形参列表含有无用参数，略

第二三两个都是TLE - 122/124的代码，可以发现即使第二个比第三个简短许多，依旧超时

可以看出每个节点都要访问两次Left和Right，经过多层嵌套，消耗了大量时间，所以需要记忆处理

存储对应节点的两个结果，以节省时间

#include<bits/stdc++.h>
using namespace std;
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) {}
};
/* AC 需简化 
typedef pair<int,int> PII;
map<TreeNode*,PII>saved;int dfs(TreeNode* root,int state,TreeNode* parent)
{if(saved.find(root)!=saved.end()){cout<<"usedsave"<<endl;if(state==1) return saved[root].second;else return max(saved[root].first,saved[root].second);}int s1=root->val,s2=0;if(root->left!=nullptr){s1+=dfs(root->left,1,root);s2+=dfs(root->left,2,root);}if(root->right!=nullptr){s1+=dfs(root->right,1,root);s2+=dfs(root->right,2,root);}saved[root]={s1,s2};if(state==1) return s2;else return max(s1,s2);
}
int dfs(TreeNode* root,int state,TreeNode* parent)// TLE 122 / 124 
{int s1=root->val,s2=0;if(root->left!=nullptr){s1+=dfs(root->left,1,root);s2+=dfs(root->left,2,root);}if(root->right!=nullptr){s1+=dfs(root->right,1,root);s2+=dfs(root->right,2,root);}if(state==1) return s2;else return max(s1,s2);
}
int dfs(TreeNode* root,int state,TreeNode* parent)// TLE 122 / 124 
{//cout<<"inroot"<<root->val<<endl;int s1=0,s2=0;//1get 2nogetif(state!=1) s1+=root->val;if(root->left!=nullptr){//cout<<"goleft_by"<<root->val<<endl;//cout<<"state"<<state<<endl;if(state==0){s1+=dfs(root->left,1,root);s2+=dfs(root->left,2,root);}if(state==1){s1+=dfs(root->left,2,root);s2+=dfs(root->left,2,root);}if(state==2){s1+=dfs(root->left,1,root);s2+=dfs(root->left,2,root);}}if(root->right!=nullptr){//cout<<"goright_by"<<root->val<<endl;//cout<<"state"<<state<<endl;if(state==0){s1+=dfs(root->right,1,root);s2+=dfs(root->right,2,root);}if(state==1){s1+=dfs(root->right,2,root);s2+=dfs(root->right,2,root);}if(state==2){s1+=dfs(root->right,1,root);s2+=dfs(root->right,2,root);}}//cout<<"outroot"<<root->val<<endl;//cout<<"max"<<s1<<" and "<<s2<<endl;return max(s1,s2);
}*/
int rob(TreeNode* root)
{int ans=dfs(root,0,nullptr);return ans;
}

实际代码：

#include<bits/stdc++.h>
using namespace std;
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) {}
};typedef pair<int,int> PII;
map<TreeNode*,PII>saved;int dfs(TreeNode* root,int state)
{if(saved.find(root)!=saved.end()){cout<<"usedsave"<<endl;if(state==1) return saved[root].second;else return max(saved[root].first,saved[root].second);}int s1=root->val,s2=0;if(root->left!=nullptr){s1+=dfs(root->left,1);s2+=dfs(root->left,2);}if(root->right!=nullptr){s1+=dfs(root->right,1);s2+=dfs(root->right,2);}saved[root]={s1,s2};if(state==1) return s2;else return max(s1,s2);
}
int rob(TreeNode* root)
{int ans=dfs(root,0);return ans;
}

限制：

• 树的节点数在 [1, 104] 范围内
• 0 <= Node.val <= 104