leecode第337题：打家劫舍III

发表于 更新于 分类于

题目：在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
原题链接

示例1：

1
2
3
4
5
6
7
8
9
10
输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例2：

1
2
3
4
5
6
7
8
9
10
输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

解题思路：

  1. 法一：类似先前的打家劫舍，对于当前位置root，可以选择，或者不选择。
  • 若选择root，就不能选择root->left和root->right，可以选择root->left->left，root->left->right，root->right->left，root->right->right。
  • 若不选择root，就能选择root->left，root->right。
  • 以上两种的最大值，就是当前位置所能抢劫到的最大金额。
  1. 法二：法一中，在计算root->left处所能抢劫到的最大金额时，需要计算root->left->left处，root->left->right处所能抢劫的最大值；而之后计算root->left->left位置所能抢劫的最大值时，又需要重新计算一遍，从而造成重复计算。因此，可用一个哈希表记录结点位置所能抢劫的最大金额，计算过的结点就无需重复计算。
  2. 法三：对于每个结点，都维护一个长度为2的数组，第0个位置记录的是不选择该结点所能取得的最大值，第1个位置记录的是选择该结点所能取得的最大值。

参考链接

代码：

  1. 法一：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int rob(TreeNode* root) {
        if (!root) return 0;
        int res = root->val;
        if (root->left) 
            res += rob(root->left->left) + rob(root->left->right);
        if (root->right)
            res += rob(root->right->left) + rob(root->right->right);
        return max(rob(root->left)+rob(root->right), res);
    }
  2. 法二：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    unordered_map<TreeNode*, int> map;
    int rob(TreeNode* root) {
        if (!root) return 0;
        if (map[root]) return map[root]; //判断哈希表中是否有该结点的记录
        int res = root->val;
        if (root->left) 
            res += rob(root->left->left) + rob(root->left->right);
        if (root->right)
            res += rob(root->right->left) + rob(root->right->right);
        res = max(rob(root->left)+rob(root->right), res);
        map[root] = res;
        return res;
    }
  3. 法三：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    vector<int> helper(TreeNode* root) {
        if (!root) return {0,0};
        vector<int> left = helper(root->left);
        vector<int> right = helper(root->right);
        return {max(left[0], left[1])+max(right[0], right[1]), root->val+left[0]+right[0]};
        // 当前结点不选择，则左右两子结点选择与否都无所谓，只要选择最大值即可；
        // 当前结点选择，则左右两子结点均不能选择，因此需要取0位置的值。
    }
    int rob(TreeNode* root) {
        vector<int> res = helper(root);
        return max(res[0], res[1]); //返回的是选择或者不选择根结点两种结果中的最大值。
    }