# House-Robber-III

Nov 26, 2017

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.

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

typedef struct {
int rob;
int norob;
}Ret;


int rob(TreeNode* root) {
Ret ret = robRec(root);
return max(ret.rob,ret.norob);
}
Ret robRec(TreeNode *root) {
Ret ret = {0,0};
if (root == nullptr) return ret;
Ret left = robRec(root->left);
Ret right = robRec(root->right);
ret.rob = left.norob + right.norob + root->val;
ret.norob = max(left.rob,left.norob) + max(right.rob,right.norob);
return ret;
}


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

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

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

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

LeetCodeLeetCodeTree

Single Number III

Merge Two Binary Trees