题目大意：
删除树节点
给你一棵以节点 0 为根节点的树，定义如下：
- 节点的总数为 nodes 个
- 第 i 个节点的值为 value[i]
- 第 i 个节点的父节点是 parent[i]
请你删除节点值之和为 0 的每一棵子树。
在完成所有删除之后，返回树中剩余节点的数目。
示例1：
输入: 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 是树的根。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1273
解题思路分析：
本题需要先对节点进行整理，题目给出了每个节点的父节点，这不利于做题，因此我们需要统计出每个节点的子节点有哪些。
统计出子节点信息后，我们使用递归方式从根节点开始查看每个节点下（包含当前节点）所有节点的和，如果当前节点（当前子树）下所有节点和为0，那么，可将当前节点下的子节点清空（相当于删除节点操作），同时当前节点值变为0。递归结束时，总和为0的子树子节点都会被删除，注意子树的根节点没被删除，只是值变为0而已。
节点删除操作结束之后，我们就可以统计剩下的节点数量，还是使用递归，从根节点开始递归统计每个节点下子节点的数量，如果当前节点为叶子节点，当值为0时，返回0，非0时，返回个数1。
实现代码：
List<Integer>[] children; // 每个节点的子节点
public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
children = new List[nodes];
for(int i=0;i<nodes;i++){
children[i]=new ArrayList<>();
}
// 统计每个节点的子节点
for(int i=0;i<nodes;i++){
int root=parent[i];
if(root==-1) continue;
children[root].add(i);
}
// 删除和为0的子树
helper(value, parent, 0);
// 统计删除后剩余节点数量，返回。
return count(0, value);
}
int helper(int[] value, int[] parent, int index){
int sum=value[index];
for(int child : children[index]){
sum+=helper(value, parent, child);
}
if(sum==0){
children[index].clear();
value[index]=0;
}
return sum;
}
int count(int index, int[] value){
if(children[index].size()==0){
return value[index]==0 ? 0:1;
}
int count=1;
for(int child : children[index]){
count+=count(child, value);
}
return count;
}本题解法执行时间为13ms。
Runtime: 13 ms, faster than 60.57% of Java online submissions for Delete Tree Nodes.
Memory Usage: 40.5 MB, less than 100.00% of Java online submissions for Delete Tree Nodes.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1273-delete-tree-nodes-解题思路分析/