题目描述
小偷又发现一个新的可行窃的地点。 这个地区只有一个入口,称为“根”。 除了根部之外,每栋房子有且只有一个父房子。 一番侦察之后,聪明的小偷意识到“这个地方的所有房屋形成了一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
在不触动警报的情况下,计算小偷一晚能盗取的最高金额。
示例 1:
3
/
2 3
3 1
能盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
3
/
4 5
/
1 3 1
能盗取的最高金额 = 4 + 5 = 9.
解题思路
用后序遍历的思想,对每一棵子树求偷窃最大金额时,分为两步来计算:
- 首先考虑最大金额中不包含根结点的情况,即分别求出根结点的左右子树的最大金额然后求和
- 接着考虑最大金额中包含根结点的情况,即以根节点为第一层,分别计算第三层上所有子树的最大金额求和,然后加上根节点的金额
比较以上两步的金额,较大值则为此子树的最大金额。这样递归求各棵子树的最大金额直到根结点,注意子树为空返回金额为0
代码
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 int rob(TreeNode* root) { 13 if(root == NULL) return 0; 14 int left = 0, right = 0, leftSon = 0, rightSon = 0; 15 if(root->left){ 16 left = rob(root->left); 17 if(root->left->left) 18 leftSon = rob(root->left->left); 19 if(root->left->right) 20 leftSon += rob(root->left->right); 21 } 22 if(root->right){ 23 right = rob(root->right); 24 if(root->right->left) 25 rightSon = rob(root->right->left); 26 if(root->right->right) 27 rightSon += rob(root->right->right); 28 } 29 return max(root->val + leftSon + rightSon, left + right); 30 } 31 };