Сложность: 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⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.
😎 Решение:
class Solution {
func deleteTreeNodes(_ nodes: Int, _ parent: [Int], _ value: [Int]) -> Int {
var tree = [Int: [Int]]()
for i in 0..<nodes {
tree[parent[i], default: []].append(i)
}
func dfs(_ node: Int) -> (Int, Int) {
var totalSum = value[node]
var totalCount = 1
if let children = tree[node] {
for child in children {
let (childSum, childCount) = dfs(child)
totalSum += childSum
totalCount += childCount
}
}
return totalSum == 0 ? (0, 0) : (totalSum, totalCount)
}
return dfs(0).1
}
}Ставь 👍 и забирай 📚 Базу знаний