The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police. 一开始的思路是先处理算出每一层的和，然后dp[i]=dp[i]+max(d[j])其中j从0到i-2，过不了样例：2,1,3,null,4，也就是说这一层和上一层不是完全互斥的，所以不能以层来做，要按每个节点来做 另外，dp[]数组先memset，并且不能再传参为dp[]的函数内memset，因为这时memset(dp,0,sizeof(dp))的sizeof(dp)是指针的size，不是数组的size。
树形dp： 维护两个dp，dp1和dp2都以当前节点为根的子树，其中dp1是偷当前节点最大值，dp2是不偷当前节点的最大值，深度优先搜索，先求子树再向上，最后结果是max(dp1[root],dp2[root])
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: map<TreeNode*,int> dp1; map<TreeNode*,int> dp2; public: void dfs(TreeNode* t){ if(t==NULL) return; dfs(t->left); dfs(t->right); dp1[t]=t->val+dp2[t->left]+dp2[t->right]; dp2[t]=max(max(dp1[t->left]+dp1[t->right],dp2[t->left]+dp2[t->right]),max(dp1[t->left]+dp2[t->right],dp2[t->left]+dp1[t->right])); } int rob(TreeNode* root) { dfs(root); return max(dp1[root],dp2[root]); } };