首页 > 代码库 > [leetcode-337-House Robber III]
[leetcode-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.
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.
思路:
Basically you want to compare which one is bigger between 1) you + sum of your grandchildren and 2) sum of your children.
用l表示下一层左子树的值,r表示下一层右子树的值。那么对于root的值只需比较
max(l + r, root->val + ll + lr + rl + rr)即可。
int rob3(TreeNode* root, int& l, int& r) { if (root == NULL)return 0; int ll = 0, lr = 0, rl = 0, rr = 0; l = rob3(root->left, ll, lr); r = rob3(root->right, rl, rr); return max(l + r, root->val + ll + lr + rl + rr); } int rob3(TreeNode* root) { int l, r; return rob3(root, l, r); }
参考:
https://discuss.leetcode.com/topic/40847/simple-c-solution
[leetcode-337-House Robber III]