[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.

Author: huadonghu

Leave a Reply

Your email address will not be published. Required fields are marked *