[leetcode] 337. House Robber III

[leetcode] 337. House Robber III

Description

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:

Input: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1Output: 9Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

分析

题目的意思是：一个小偷在一个二叉树结构的房子里抢劫，但是相邻的房子不能抢，求能够抢到的最大值。

二叉树的题目，很显然是一个递归搜索的题目。因为当前的计算需要依赖之前的结果，那么我们对于某一个节点，如果其左子节点存在，我们通过递归调用函数，算出不包含左子节点返回的值，同理，如果右子节点存在，算出不包含右子节点返回的值，那么此节点的最大值可能有两种情况，一种是该节点值加上不包含左子节点和右子节点的返回值之和，另一种是左右子节点返回值之和不包含当期节点值，取两者的较大值返回即可。由于递归计算有重复，我们利用map储存计算过的结点（常规做法），来减少搜索空间，减少计算量。

代码

/** * 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: int rob(TreeNode* root) { unordered_map mp; return dfs(root,mp); } int dfs(TreeNode* root,unordered_map &mp){ if(!root){ return 0; } if(mp.count(root)){ return mp[root]; } int val=0; if(root->left){ val+=dfs(root->left->left,mp)+dfs(root->left->right,mp); } if(root->right){ val+=dfs(root->right->left,mp)+dfs(root->right->right,mp); } val=max(val+root->val,dfs(root->left,mp)+dfs(root->right,mp)); mp[root]=val; return val; }};

参考文献

​​[LeetCode] House Robber III 打家劫舍之三​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。