Задача: 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⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

def deleteTreeNodes(nodes, parent, value):
    from collections import defaultdict, deque
    
    tree = defaultdict(list)
    for i in range(nodes):
        if parent[i] != -1:
            tree[parent[i]].append(i)
    
    def dfs(node):
        total_sum = value[node]
        total_count = 1
        for child in tree[node]:
            child_sum, child_count = dfs(child)
            total_sum += child_sum
            total_count += child_count
        if total_sum == 0:
            return 0, 0
        return total_sum, total_count
    
    return dfs(0)[1]

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