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 1Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3 / \ 4 5 / \ \ 1 3 1Maximum amount of money the thief can rob = 4 + 5 = 9.
[Thoughts]
这就可以归结为树的递归遍历问题。对于任意一个节点,如下图三角虚线内,该子树的最大值一定是下面两个可能:
- root + left_left + left_right + right_left + right_right
- left + right
所以对于任意一个节点,只要递归的调用这个关系,就可以得到解。
[Code]
1: int rob(TreeNode* root) {
2: if(root == NULL) return 0;
3:
4: int val = 0;
5:
6: if(root->left) {
7: val += rob(root->left->left) + rob(root->left->right);
8: }
9:
10: if(root->right) {
11: val += rob(root->right->left) + rob(root->right->right);
12: }
13:
14: return max(root->val + val, rob(root->left) + rob(root->right));
15: }
No comments:
Post a Comment