Keshawn_lu's Blog

Leetcode 337. 打家劫舍 III

字数统计: 608阅读时长: 2 min
2020/08/05 Share

题目简介:

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

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

示例 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.

思路:

动态规划,由于每个结点都有选中和未选中的状态,所以定义两个哈希表(哈希映射)。

choose[root]代表以root作为根节点并选中root时所能盗取的最高金额。

unchoose[root]代表以root作为根节点,并且未选中root时所能盗取的最高金额。

若选中了根节点root,则choose[root] = root -> val + unchoose[root -> left] + unchoose[root -> right],即根节点的值加上未选中左右孩子时的金额和。

若未选中根节点root,则左右孩子可选也可不选,所以取左右孩子选或不选的最大值即可,即unchoose[root] = max(choose[root -> left], unchoose[root -> left]) + max(choose[root -> right], unchoose[root -> right])

通过深度优先遍历的方法后序遍历这棵二叉树,即可得到每个结点的两个值。(需要由下往上的动态规划)

最后返回choose[root]unchoose[root]的较大值即可。

代码如下:

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(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

unordered_map<TreeNode*, int> choose, unchoose;

void dfs(TreeNode* root){

if(root == NULL)
return;

dfs(root -> left);
dfs(root -> right);

//选了根节点
choose[root] = root -> val + unchoose[root -> left] + unchoose[root -> right];

//未选根节点
unchoose[root] = max(choose[root -> left], unchoose[root -> left]) + max(choose[root -> right], unchoose[root -> right]);

}

int rob(TreeNode* root) {

dfs(root);
return choose[root] > unchoose[root] ? choose[root] : unchoose[root];
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: