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返回），也就是偷与不偷可以获得的最大利益。

1. 当偷当前这座房子时，意味着与这座房子相连的节点都不能偷（当前节点的子节点），所以当偷这座房子时：
   能产生的利益 = 当前节点值 + 不偷当前节点两个子节点的利益

2. 当不偷当前这座房子时，不偷当前节点产生的利益应该从以下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);
    }