第60天。

今天的题目是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:

1
 3
2
/ \

2 3 \
3 1

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

1
 3
2
/ \

4 5 / \
1 3 1

Maximum amount of money the thief can rob = 4 + 5 = 9.

之前有刷过House robber,上次是一道dp的题目，这次看起来有点像是dp的题目，但是其实不是。

我们考虑当前节点root,我们有两种选择：

• 不偷root:这意味着我们对root的孩子没有限制（即可以偷也可以不偷）。
• 偷root：这意味着我们不能偷root的孩子。

从上面的分析可以看出，对于一个节点，我们可能需要返回两个值，一个是偷了root所得到的money,一个是不偷root所得到的money.我们可以用一个结构体来表示:

1
typedef struct {
2
    int rob;
3
    int norob;
4
}Ret;

假设我们现在得到了root左孩子和右孩子的Ret了，我们现在要构建root本身的Ret.显然rob = left.norob + right.norob + root->val.然后还有norob,这个很容易就写成norob = left.rob + right.rob,这样写就假定了rob > norob的，在上面的分析中，我们是说我们对root的孩子没有限制，既然没有限制，就可以偷也可以不偷，所以norob = max(left.rob,left.norob) + max(right.rob,right.norob).

1
int rob(TreeNode* root) {
2
    Ret ret = robRec(root);
3
    return max(ret.rob,ret.norob);
4
}
5
Ret robRec(TreeNode *root) {
6
    Ret ret = {0,0};
7
    if (root == nullptr) return ret;
8
    Ret left = robRec(root->left);
9
    Ret right = robRec(root->right);
10
    ret.rob = left.norob + right.norob + root->val;
11
    ret.norob = max(left.rob,left.norob) + max(right.rob,right.norob);
12
    return ret;
13
}

dicuss中的解法大都是这个思路，只是写法不同而已，有一个写法比较有趣：

1
public int rob(TreeNode root) {
2
    if (root == null) return 0;
3
    return Math.max(robInclude(root), robExclude(root));
4
}
5

6
public int robInclude(TreeNode node) {
7
    if(node == null) return 0;
8
    return robExclude(node.left) + robExclude(node.right) + node.val;
9
}
10

11
public int robExclude(TreeNode node) {
12
    if(node == null) return 0;
13
    return rob(node.left) + rob(node.right);
14
}