Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

👨‍💻 Алгоритм:

1⃣Постройте дерево из заданных узлов, значений и родителей.

2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю.

3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

import java.util.*;

public class Solution {
    public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 0; i < nodes; i++) {
            tree.computeIfAbsent(parent[i], k -> new ArrayList<>()).add(i);
        }

        return dfs(0, tree, value)[1];
    }

    private int[] dfs(int node, Map<Integer, List<Integer>> tree, int[] value) {
        int totalSum = value[node];
        int totalCount = 1;
        if (tree.containsKey(node)) {
            for (int child : tree.get(node)) {
                int[] childResult = dfs(child, tree, value);
                totalSum += childResult[0];
                totalCount += childResult[1];
            }
        }
        if (totalSum == 0) {
            return new int[]{0, 0};
        }
        return new int[]{totalSum, totalCount};
    }
}

Ставь 👍 и забирай 📚 Базу знаний