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

😎 Решение:

function deleteTreeNodes($nodes, $parent, $value) {
    $tree = [];
    for ($i = 0; $i < $nodes; $i++) {
        if (!isset($tree[$parent[$i]])) $tree[$parent[$i]] = [];
        $tree[$parent[$i]][] = $i;
    }

    function dfs($node, &$tree, &$value) {
        $totalSum = $value[$node];
        $totalCount = 1;
        if (isset($tree[$node])) {
            foreach ($tree[$node] as $child) {
                list($childSum, $childCount) = dfs($child, $tree, $value);
                $totalSum += $childSum;
                $totalCount += $childCount;
            }
        }
        return $totalSum == 0 ? [0, 0] : [$totalSum, $totalCount];
    }

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

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