题解：定义状态dp[i][0/1]，dp[i][0]表示选择节点i，dp[i][1]表示不选节点i。
通过树的后序遍历从根往上走，
状态转移方程 dp[i][0]=i->val+dp[i->left][1]+dp[i->right][1];
dp[i][1]=max(dp[i->left][0],dp[i->left][1])+max(dp[i->right][0],dp[i->right][1]);
code:
class Solution { public: unordered_map <TreeNode*, int> f,g;//f表示选当前节点的最好状态，g表示不选当前节点的最好状态。 int rob(TreeNode* root) { dfs(root); return max(f[root],g[root]); } void dfs(TreeNode* root){ if(!root) return; dfs(root->left); dfs(root->right); f[root]=root->val+g[root->left]+g[root->right]; g[root]=max(f[root->left],g[root->left])+max(f[root->right],g[root->right]); } };
树形dp入门题（Leetcode 337. 打家劫舍 III）
原文：https://www.cnblogs.com/Accepting/p/13587132.html