苏州全网网站建设,今天正式封城,长沙模板建站定制,上海建设工程 U盘登录哪个网站文章目录1. 题目2. 解题2.1 取巧解2.2 拓扑排序2.3 建图DFS1. 题目
给你一棵以节点 0 为根节点的树#xff0c;定义如下#xff1a;
节点的总数为 nodes 个#xff1b;
第 i 个节点的值为 value[i] #xff1b;
第 i 个节点的父节点是 parent[i] 。
请你删除节点值之和为…
文章目录1. 题目2. 解题2.1 取巧解2.2 拓扑排序2.3 建图DFS1. 题目
给你一棵以节点 0 为根节点的树定义如下
节点的总数为 nodes 个
第 i 个节点的值为 value[i]
第 i 个节点的父节点是 parent[i] 。
请你删除节点值之和为 0 的每一棵子树。在完成所有删除之后返回树中剩余节点的数目。
示例
输入nodes 7,
parent [-1,0,0,1,2,2,2],
value [1,-2,4,0,-2,-1,-1]
输出2提示
1 nodes 10^4
-10^5 value[i] 10^5
parent.length nodes
parent[0] -1 表示节点 0 是树的根。来源力扣LeetCode 链接https://leetcode-cn.com/problems/delete-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 取巧解
数据很特殊数据尾部为更深的节点逆序遍历即是自底向上该解法不通用
class Solution {
public:int deleteTreeNodes(int nodes, vectorint parent, vectorint value) {int i, n parent.size();vectorint count(n,1);for(i n-1; i 0; --i){if(value[i]0)count[i] 0;//自己子树和为0删除节点if(parent[i] ! -1){value[parent[i]] value[i];//值加给父节点count[parent[i]] count[i];//父节点底下不为0的节点个数}}return count[0];}
};60 ms 21.1 MB
2.2 拓扑排序
class Solution {
public:int deleteTreeNodes(int nodes, vectorint parent, vectorint value) {int i, n parent.size();vectorint indegree(n,0);for(i 0; i n; i)if(parent[i] ! -1)indegree[parent[i]];queueint q;for(i 0; i n; i)if(indegree[i] 0)q.push(i);vectorint count(n,1);while(!q.empty()){int tp q.front();q.pop();if(value[tp]0)count[tp] 0;if(parent[tp] -1)continue;if(--indegree[parent[tp]]0)q.push(parent[tp]);value[parent[tp]] value[tp];count[parent[tp]] count[tp];}return count[0];}
};88 ms 22.2 MB
2.3 建图DFS
class Solution {vectorvectorint edges;vectorint count;
public:int deleteTreeNodes(int nodes, vectorint parent, vectorint value) {int i, n parent.size();edges.resize(n);count vectorint(n,1);for(i 0; i n; i)if(parent[i] ! -1)edges[parent[i]].push_back(i);dfs(0, parent, value);return count[0];}void dfs(int id, vectorint parent, vectorint value){for(int next : edges[id]){dfs(next, parent, value);}if(value[id]0)count[id] 0;if(parent[id] ! -1){value[parent[id]] value[id];count[parent[id]] count[id];}}
};96 ms 29.4 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
