第60天。
今天的题目是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:
1 32/ \
2 3
\
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7. Example 2:
1 32/ \
4 5
/ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
之前有刷过House robber
,上次是一道dp
的题目,这次看起来有点像是dp
的题目,但是其实不是。
我们考虑当前节点root
,我们有两种选择:
- 不偷
root
:这意味着我们对root
的孩子没有限制(即可以偷也可以不偷)。 - 偷
root
:这意味着我们不能偷root
的孩子。
从上面的分析可以看出,对于一个节点,我们可能需要返回两个值,一个是偷了root
所得到的money
,一个是不偷root
所得到的money
.我们可以用一个结构体来表示:
1typedef struct {2 int rob;3 int norob;4}Ret;
假设我们现在得到了root
左孩子和右孩子的Ret
了,我们现在要构建root
本身的Ret
.显然rob = left.norob + right.norob + root->val
.然后还有norob
,这个很容易就写成norob = left.rob + right.rob
,这样写就假定了rob > norob
的,在上面的分析中,我们是说我们对root
的孩子没有限制,既然没有限制,就可以偷也可以不偷,所以norob = max(left.rob,left.norob) + max(right.rob,right.norob)
.
1int rob(TreeNode* root) {2 Ret ret = robRec(root);3 return max(ret.rob,ret.norob);4}5Ret robRec(TreeNode *root) {6 Ret ret = {0,0};7 if (root == nullptr) return ret;8 Ret left = robRec(root->left);9 Ret right = robRec(root->right);10 ret.rob = left.norob + right.norob + root->val;11 ret.norob = max(left.rob,left.norob) + max(right.rob,right.norob);12 return ret;13}
dicuss
中的解法大都是这个思路,只是写法不同而已,有一个写法比较有趣:
1public int rob(TreeNode root) {2 if (root == null) return 0;3 return Math.max(robInclude(root), robExclude(root));4}5
6public int robInclude(TreeNode node) {7 if(node == null) return 0;8 return robExclude(node.left) + robExclude(node.right) + node.val;9}10
11public int robExclude(TreeNode node) {12 if(node == null) return 0;13 return rob(node.left) + rob(node.right);14}