0%

[Leetcode]337. House Robber III(C++)

题目描述

题目链接:337. 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.

例子

例子 1

Input: [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

例子 2

Input: [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

解题思路

这道题可以用动态规划的思路来做,对于一个根结点 root 而言,情况有两种:

  • 使用相隔一层之后的结果加上当前节点的值
  • 直接使用相邻层的结果

因此转移方程为:

rob(root) = max(root->val + rob(two childrens of (root->left)) + rob(two children of root->right), rob(root->left) + rob(root->right))

为了避免重复计算,我们可以使用一个哈希表来存储每个节点的 rob 结果。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/

#include <unordered_map>
class Solution {
public:
int rob(TreeNode* root) {
if (!root) return 0;
if (hmap.find(root) != hmap.end()) return hmap[root];
int curr_sum = root->val;
if (root->left) {
curr_sum += rob(root->left->left);
curr_sum += rob(root->left->right);
}
if (root->right) {
curr_sum += rob(root->right->left);
curr_sum += rob(root->right->right);
}

int prev_sum = rob(root->left) + rob(root->right);
hmap[root] = max(curr_sum, prev_sum);
return hmap[root];
}

private:
std::unordered_map<TreeNode*, int> hmap;
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 337.HouseRobberIII.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions