leetcode 337. 打家劫舍 III

题目链接：leetcode 337

1.题目

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

2.示例&数据范围

1）示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

2）示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

3）提示：
树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104

3.分析

本质上是一个树状dp问题，可以使用两个unordered_map来存储当前根节点被选取/未被选取的最高金额，然后左子树和右子树递推即可

4.代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans=0;unordered_map <TreeNode*, int> f,g;void get_dfs(TreeNode* root){if(root==NULL) return;int fx=0,fy=0,rx=0,ry=0;get_dfs(root->left);get_dfs(root->right);if(root->left!=NULL){fx=f[root->left];rx=g[root->left];}if(root->right!=NULL){fy=f[root->right];ry=g[root->right];}f[root]=max(fx,rx)+max(fy,ry);g[root]=fx+fy+root->val;}int rob(TreeNode* root) {get_dfs(root);return max(f[root],g[root]);}
};