# [LeetCode] 1273. Delete Tree Nodes

## Solution

Do dfs on tree and check on backtracking if sum from children to current node equals to 0, if yes, trim it and its children by return count = 0 to its parent.

## Code

```
class Solution {
HashSet<Integer>[] adj;
int[] value;
public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
this.adj = new HashSet[nodes];
this.value = value;
for(int i = 0; i < nodes; i++) {
adj[i] = new HashSet<Integer>();
}
for(int i = 1; i < parent.length; i++) {
adj[parent[i]].add(i);
}
return dfs(0)[1];
}
private int[] dfs(int root) {
int count = 1;
int sum = value[root];
for(int x : adj[root] ) {
int[] tmp = dfs(x);
sum += tmp[0];
count += tmp[1];
}
if (sum == 0) {
count = 0;
}
return new int[]{sum, count};
}
}
```

Runtime: 12 ms, faster than 39.42% of Java online submissions for Delete Tree Nodes.

Memory Usage: 48.2 MB, less than 100.00% of Java online submissions for Delete Tree Nodes.

**It would be super slow if we don’t build a tree.**

```
class Solution {
int[] parent;
int[] value;
public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
this.parent = parent;
this.value = value;
return dfs(0)[1];
}
private int[] dfs(int root) {
int count = 1;
int sum = value[root];
for(int i = 1; i < parent.length; i++) {
if(parent[i] == root) {
int[] tmp = dfs(i);
sum += tmp[0];
count += tmp[1];
}
}
if (sum == 0) {
count = 0;
}
return new int[]{sum, count};
}
}
```

Runtime: 884 ms, faster than 5.29% of Java online submissions for Delete Tree Nodes.

Memory Usage: 41.2 MB, less than 100.00% of Java online submissions for Delete Tree Nodes.