LeetCode House Robber III 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. Example 1:

     3
    / \
   2   3
    \   \
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7. Example 2:

     3
    / \
   4   5
  / \   \
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9. Credits: Special thanks to @dietpepsi for adding this problem and creating all test cases.

---

这次要偷的房子分布在一棵二叉树上。。。 规则是有边相连的两个节点不能同时被偷，问最多能偷到多少钱。 我开始想的和LeetCode House Robber类似，一个节点要么偷，要么不偷。不偷得到的钱是上一个节点偷或不偷的最大值；偷得到的钱是上一个节点不偷加上该节点的钱数。使用递归的方法求解。 代码如下： [cpp] class Solution { private: void dfs(TreeNode* root, int& norobsum, int& robsum) { int nrs = max(norobsum, robsum); int rs = norobsum + root->val; norobsum = nrs; robsum = rs; if (root->left)dfs(root->left, norobsum, robsum); if (root->right)dfs(root->right, norobsum, robsum); } public: int rob(TreeNode* root) { if (!root)return 0; int norobsum = 0, robsum = 0; dfs(root, norobsum, robsum); return max(norobsum, robsum); } }; [/cpp] 本代码提交WA，错误样例如下：

     1
    / \
   2   3

令m[i]=(u,v)表示截至目前偷i节点得到u钱，不偷得到v钱。则m[1]=(1,0)，递归进入左孩子，m[2]=(2+0,max(1,0))=(2,1)，递归进入右孩子，m[3]=(3+1,max(2,1))=(4,2)。导致算出来的结果是4。这是因为3号节点偷的时候，其实不是3+1，1号节点的状态不能简单等价于2号节点的状态。 正确的做法应该是这样的，对于节点i，先算到左右节点偷或者不偷的钱数，即m[l]=(lrs,lnrs)和m[r]=(rrs，rnrs)。那么i偷的话，则左右节点都不能偷了=lnrs+rnrs+i.val；如果i不偷的话，则左右节点都可以偷或者不偷=max(lnrs,lrs)+max(rnrs,rrs)，所以m[i]=(lnrs+rnrs+i.val, max(lnrs,lrs)+max(rnrs,rrs))。 代码如下： [cpp] class Solution { private: void dfs(TreeNode* root, int& norobsum, int& robsum) { int lnrs = 0, lrs = 0, rnrs = 0, rrs = 0; if (root->left)dfs(root->left, lnrs, lrs); if (root->right)dfs(root->right, rnrs, rrs); norobsum = max(lnrs, lrs) + max(rnrs, rrs); robsum = lnrs + rnrs + root->val; } public: int rob(TreeNode* root) { if (!root)return 0; int norobsum = 0, robsum = 0; dfs(root, norobsum, robsum); return max(norobsum, robsum); } }; [/cpp] 本代码提交AC，用时16MS。]]>