Сложность: 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]
Ставь 👍 и забирай 📚 Базу знаний