House Robber III解题报告
Description:
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:
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.
Link:
https://leetcode.com/problems/house-robber-iii/description/
解题方法：
遍历每个节点，相当于给每个房子踩点。每个节点需要返回两个值（用pair返回），也就是偷与不偷可以获得的最大利益。
-
当偷当前这座房子时，意味着与这座房子相连的节点都不能偷（当前节点的子节点），所以当偷这座房子时：
能产生的利益 = 当前节点值 + 不偷当前节点两个子节点的利益 -
当不偷当前这座房子时，不偷当前节点产生的利益应该从以下4种情况中取最大值：
能产生的利益 = 偷左孩子产生的利益 + 偷右孩子产生的利益能产生的利益 = 不偷左孩子产生的利益 + 不偷右孩子产生的利益能产生的利益 = 偷左孩子产生的利益 + 不偷右孩子产生的利益能产生的利益 = 不偷左孩子产生的利益 + 偷右孩子产生的利益
每次遍历每个节点都应该返回以上1和2两个值。
Time Complexity：
O(N)
完整代码：
int rob(TreeNode* root)
{
pair<int, int> result = helper(root);
return result.first > result.second ? result.first : result.second;
}
pair<int, int> helper(TreeNode* root)
{
if(!root)
return pair<int, int> (0, 0);
pair<int, int> leftReturn = helper(root->left);
pair<int, int> rightReturn = helper(root->right);
int get = root->val + leftReturn.second + rightReturn.second;
int nGet = max(leftReturn.first + rightReturn.first, leftReturn.second + rightReturn.second);
nGet = max(max(nGet, leftReturn.first + rightReturn.second), leftReturn.second + rightReturn.first);
return pair<int, int> (get, nGet);
}
