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.

分析参考

分析，主要是两种情况，一种是包含根节点，另一种是不包含根节点；
用pair分别存储下这两种情况。

               4
              /
             1
            /
           2
          /
         3

但在这种情况下得到的却是6，不是正确答案7，想了想，主要是因为如果按照下面的代码计算的总是隔层相加的结果，而未考虑到隔两层的情况；

刚开始写的代码为

class Solution {
public:
    int rob(TreeNode* root) {
        return max(robber(root).second,robber(root).first);
    }
    pair<int, int> robber(TreeNode *r){
        pair<int, int> p = make_pair(0, 0);

        if(r){
            auto p_L = robber(r->left);
            auto p_R = robber(r->right);

            //first存储的是不包括根节点的情况
            p.first = p_L.second + p_R.second;
            //second存储的是包含根节点的情况。
            p.second = p_L.first + p_R.first + r->val;
        }
        return p;
    }
};

将pair改为存储所有情况最大值(包含不包括根节点的情况)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        return robber(root).second;
    }
    pair<int, int> robber(TreeNode *r){
        pair<int, int> p = make_pair(0, 0);

        if(r){
            auto p_L = robber(r->left);
            auto p_R = robber(r->right);

            //first存储的是不包括根节点的情况
            p.first = p_L.second + p_R.second;
            //second存储的是以当前节点为根可以达到的最大值(可以不包括此根节点)
            p.second = max(p.first, p_L.first + p_R.first + r->val);
        }
        return p;
    }
};

public int rob(TreeNode root) {
    int[] res = robSub(root);
    return Math.max(res[0], res[1]);
}

private int[] robSub(TreeNode root) {
    if (root == null) {
        return new int[2];
    }

    int[] left = robSub(root.left);
    int[] right = robSub(root.right);

    int[] res = new int[2];
    //此处res[0]考虑的情况为左子树包括根节点，不包括根节点，同样滴，右子树包括根节点，不包括根节点
    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];

    return res;
}