类似于建设通的网站,个人域名能做网站吗,延边网站建设,济南做网站哪家好题目链接#xff1a;leetcode 337
1.题目
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口#xff0c;我们称之为 root 。
除了 root 之外#xff0c;每栋房子有且只有一个“父“房子与之相连。一番侦察之后#xff0c;聪明的小偷意识到“这个地方的所有房屋的…题目链接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 ans0;unordered_map TreeNode*, int f,g;void get_dfs(TreeNode* root){if(rootNULL) return;int fx0,fy0,rx0,ry0;get_dfs(root-left);get_dfs(root-right);if(root-left!NULL){fxf[root-left];rxg[root-left];}if(root-right!NULL){fyf[root-right];ryg[root-right];}f[root]max(fx,rx)max(fy,ry);g[root]fxfyroot-val;}int rob(TreeNode* root) {get_dfs(root);return max(f[root],g[root]);}
};
