泉州模板建站定制,怎么做游戏推广网站,门户网站建设服务收费,手机百度2022年新版本下载文章目录1. 题目2. 解题1. 题目
小扣有一个根结点为 root 的二叉树模型#xff0c;初始所有结点均为白色#xff0c;可以用蓝色染料给模型结点染色#xff0c;模型的每个结点有一个 val 价值。 小扣出于美观考虑#xff0c;希望最后二叉树上每个蓝色相连部分的结点个数不能…
文章目录1. 题目2. 解题1. 题目
小扣有一个根结点为 root 的二叉树模型初始所有结点均为白色可以用蓝色染料给模型结点染色模型的每个结点有一个 val 价值。 小扣出于美观考虑希望最后二叉树上每个蓝色相连部分的结点个数不能超过 k 个求所有染成蓝色的结点价值总和最大是多少
示例 1
输入root [5,2,3,4], k 2
输出12
解释结点 5、3、4 染成蓝色获得最大的价值 53412示例 2
输入root [4,1,3,9,null,null,2], k 2
输出16
解释结点 4、3、9 染成蓝色获得最大的价值 43916提示
1 k 10
1 val 10000
1 结点数量 10000来源力扣LeetCode 链接https://leetcode-cn.com/problems/er-cha-shu-ran-se-UGC 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
自底向上 DPunordered_mapTreeNode*, unordered_mapint, int m; 定义每个节点TreeNode*该节点相连的蓝色点数量最大的和
/*** 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 {unordered_mapTreeNode*, unordered_mapint, int m;//每个节点TreeNode*该节点相连的蓝色点数量最大的和int n;
public:int maxValue(TreeNode* root, int k) {n k;dfs(root);int ans 0;for(auto it m[root].begin(); it ! m[root].end(); it){int v1 it-second;ans max(ans, v1);}return ans;}void dfs(TreeNode* root){if(!root) return;dfs(root-left);dfs(root-right);if(m.count(root-left) m.count(root-right)){for(auto it m[root-left].begin(); it ! m[root-left].end(); it){int n1 it-first, v1 it-second;for(auto it1 m[root-right].begin(); it1 ! m[root-right].end(); it1){int n2 it1-first, v2 it1-second;// root 不涂色root相连的有色节点为0m[root][0] max(m[root][0], v1v2);if(n1n2 n){ // root 涂色m[root][n1n21] max(m[root][n1n21], v1v2root-val);}}}}else if(m.count(root-left)){for(auto it m[root-left].begin(); it ! m[root-left].end(); it){int n1 it-first, v1 it-second;// root 不涂色root相连的有色节点为0m[root][0] max(m[root][0], v1);if(n1 n){ // root 涂色m[root][n11] max(m[root][n11], v1root-val);}}}else if(m.count(root-right)){for(auto it m[root-right].begin(); it ! m[root-right].end(); it){int n1 it-first, v1 it-second;// root 不涂色root相连的有色节点为0m[root][0] max(m[root][0], v1);if(n1 n){ // root 涂色m[root][n11] max(m[root][n11], v1root-val);}}}else{ // root 不涂色root相连的有色节点为0m[root][0] max(m[root][0], 0);// root 涂色m[root][1] max(m[root][1], root-val);}}
};880 ms 249.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
