1273. Delete Tree Nodes

LeetCode medium оригинал: C# #array #csharp #graph #hash-table #leetcode #medium #tree

LeetCode Static

Дерево, укорененное в узле 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

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
public class Solution {
    public int DeleteTreeNodes(int nodes, int[] parent, int[] value) {
        var tree = new Dictionary<int, List<int>>();
        for (int i = 0; i < nodes; i++) {
            if (!tree.ContainsKey(parent[i])) tree[parent[i]] = new List<int>();
            tree[parent[i]].Add(i);
        }
        (int, int) Dfs(int node) {
            int totalSum = value[node];
            int totalCount = 1;
            if (tree.ContainsKey(node)) {
                foreach (int child in tree[node]) {
                    var (childSum, childCount) = Dfs(child);
                    totalSum += childSum;
                    totalCount += childCount;
                }
            }
            return totalSum == 0 ? (0, 0) : (totalSum, totalCount);
        }
        return Dfs(0).Item2;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int DeleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        var tree = new unordered_map<int, List<int>>();
        for (int i = 0; i < nodes; i++) {
            if (!tree.count(parent[i])) tree[parent[i]] = new List<int>();
            tree[parent[i]].push_back(i);
        }
        (int, int) Dfs(int node) {
            int totalSum = value[node];
            int totalCount = 1;
            if (tree.count(node)) {
                foreach (int child in tree[node]) {
                    var (childSum, childCount) = Dfs(child);
                    totalSum += childSum;
                    totalCount += childCount;
                }
            }
            return totalSum == 0 ? (0, 0) : (totalSum, totalCount);
        }
        return Dfs(0).Item2;
    }
}

Java решение

сопоставлено/оригинал

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};
    }
}

JavaScript решение

сопоставлено/оригинал

var deleteTreeNodes = function(nodes, parent, value) {
    let tree = new Map();
    for (let i = 0; i < nodes; i++) {
        if (!tree.has(parent[i])) tree.set(parent[i], []);
        tree.get(parent[i]).push(i);
    }

    function dfs(node) {
        let totalSum = value[node];
        let totalCount = 1;
        if (tree.has(node)) {
            for (let child of tree.get(node)) {
                let [childSum, childCount] = dfs(child);
                totalSum += childSum;
                totalCount += childCount;
            }
        }
        return totalSum === 0 ? [0, 0] : [totalSum, totalCount];
    }

    return dfs(0)[1];
};

Python решение

сопоставлено/оригинал

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]

Go решение

сопоставлено/оригинал

func deleteTreeNodes(nodes int, parent []int, value []int) int {
    tree := make(map[int][]int)
    for i := 0; i < nodes; i++ {
        tree[parent[i]] = append(tree[parent[i]], i)
    }

    var dfs func(node int) (int, int)
    dfs = func(node int) (int, int) {
        totalSum := value[node]
        totalCount := 1
        for _, child := range tree[node] {
            childSum, childCount := dfs(child)
            totalSum += childSum
            totalCount += childCount
        }
        if totalSum == 0 {
            return 0, 0
        }
        return totalSum, totalCount
    }

    _, count := dfs(0)
    return count
}

Algorithm

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.