# [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 {
int[] value;
public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
this.value = value;
for(int i = 0; i < nodes; i++) {
}
for(int i = 1; i < parent.length; i++) {
}
return dfs(0);
}

private int[] dfs(int root) {
int count = 1;
int sum = value[root];
for(int x : adj[root] ) {
int[] tmp = dfs(x);
sum += tmp;
count += tmp;
}
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);
}

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;
count += tmp;
}
}
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. 