LeetCode House Robber III

LeetCode 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.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.


这次要偷的房子分布在一棵二叉树上。。。

规则是有边相连的两个节点不能同时被偷,问最多能偷到多少钱。

我开始想的和LeetCode House Robber类似,一个节点要么偷,要么不偷。不偷得到的钱是上一个节点偷或不偷的最大值;偷得到的钱是上一个节点不偷加上该节点的钱数。使用递归的方法求解。

代码如下:

class Solution {
private:
	void dfs(TreeNode* root, int& norobsum, int& robsum) {
		int nrs = max(norobsum, robsum);
		int rs = norobsum + root->val;
		norobsum = nrs;
		robsum = rs;
		if (root->left)dfs(root->left, norobsum, robsum);
		if (root->right)dfs(root->right, norobsum, robsum);
	}
public:
	int rob(TreeNode* root) {
		if (!root)return 0;
		int norobsum = 0, robsum = 0;
		dfs(root, norobsum, robsum);
		return max(norobsum, robsum);
	}
};

本代码提交WA,错误样例如下:

     1
    / \
   2   3

令m[i]=(u,v)表示截至目前偷i节点得到u钱,不偷得到v钱。则m[1]=(1,0),递归进入左孩子,m[2]=(2+0,max(1,0))=(2,1),递归进入右孩子,m[3]=(3+1,max(2,1))=(4,2)。导致算出来的结果是4。这是因为3号节点偷的时候,其实不是3+1,1号节点的状态不能简单等价于2号节点的状态。

正确的做法应该是这样的,对于节点i,先算到左右节点偷或者不偷的钱数,即m[l]=(lrs,lnrs)和m[r]=(rrs,rnrs)。那么i偷的话,则左右节点都不能偷了=lnrs+rnrs+i.val;如果i不偷的话,则左右节点都可以偷或者不偷=max(lnrs,lrs)+max(rnrs,rrs),所以m[i]=(lnrs+rnrs+i.val, max(lnrs,lrs)+max(rnrs,rrs))。

代码如下:

class Solution {
private:
	void dfs(TreeNode* root, int& norobsum, int& robsum) {
		int lnrs = 0, lrs = 0, rnrs = 0, rrs = 0;
		if (root->left)dfs(root->left, lnrs, lrs);
		if (root->right)dfs(root->right, rnrs, rrs);
		norobsum = max(lnrs, lrs) + max(rnrs, rrs);
		robsum = lnrs + rnrs + root->val;
	}
public:
	int rob(TreeNode* root) {
		if (!root)return 0;
		int norobsum = 0, robsum = 0;
		dfs(root, norobsum, robsum);
		return max(norobsum, robsum);
	}
};

本代码提交AC,用时16MS。

Leave a Reply

Your email address will not be published. Required fields are marked *