在上次打劫完一条街道之后和一圈房屋后, 小偷又发现了一个新的可行窃的地区. 这个地区只有一个入口, 我们称之为 "根". 除了 "根" 之外, 每栋房子有且只有一个 "父" 房子与之相连. 一番侦察之后, 聪明的小偷意识到 "这个地方的所有房屋的排列类似于一棵二叉树". 如果两个直接相连的房子在同一天晚上被打劫, 房屋将自动报警.
计算在不触动警报的情况下, 小偷一晚能够盗取的最高金额.
示例 1:
输入: [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- * };
- */
- class Solution {
- public:
- vector<int>a;
- vector<int>dp[2];
- void dfs(TreeNode* root){
- if(root!=NULL){
- a.push_back(root->val);
- root->val=a.size()-1;
- dfs(root->left);
- dfs(root->right);
- }
- }
- void dfs2(TreeNode* root){
- if(root!=NULL){
- dp[0][root->val]=0;
- dp[1][root->val]=a[root->val];
- if(root->left!=NULL){
- dfs2(root->left);
- dp[0][root->val]+=max(dp[0][root->left->val],dp[1][root->left->val]);
- dp[1][root->val]+=dp[0][root->left->val];
- }
- if(root->right!=NULL){
- dfs2(root->right);
- dp[0][root->val]+=max(dp[0][root->right->val],dp[1][root->right->val]);
- dp[1][root->val]+=dp[0][root->right->val];
- }
- }
- }
- int rob(TreeNode* root) {
- if(root==NULL)return 0;
- dfs(root);
- for(int i=0;i<a.size();i++){
- dp[0].push_back(0);
- dp[1].push_back(0);
- }
- dfs2(root);
- return max(dp[0][0],dp[1][0]);
- }
- };
来源: http://www.bubuko.com/infodetail-3486379.html