README.md

1273. 删除树节点

English Version

题目描述

给你一棵以节点 0 为根节点的树，定义如下：

• 节点的总数为 nodes 个；
• 第 i 个节点的值为 value[i] ；
• 第 i 个节点的父节点是 parent[i] 。

请你删除节点值之和为 0 的每一棵子树。

在完成所有删除之后，返回树中剩余节点的数目。

 

示例 1：

输入：nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
输出：2

示例 2：

输入：nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-2]
输出：6

示例 3：

输入：nodes = 5, parent = [-1,0,1,0,0], value = [-672,441,18,728,378]
输出：5

示例 4：

输入：nodes = 5, parent = [-1,0,0,1,1], value = [-686,-842,616,-739,-746]
输出：5

 

提示：

• 1 <= nodes <= 10^4
• parent.length == nodes
• 0 <= parent[i] <= nodes - 1
• parent[0] == -1 表示节点 0 是树的根。
• value.length == nodes
• -10^5 <= value[i] <= 10^5
• 题目输入数据 保证 是一棵 有效的树 。

解法

先构建图。

然后对于树中的每一个节点 u，我们通过深度优先搜索的方法，递归地搜索它的所有子节点 v，计算出以 v 为根的子树的节点数目和权值之和。在这之后，我们将子节点的值分别进行累加，就可以得到以 u 为根的子树的节点数目和权值之和。如果权值之和为零，那么以 u 为根的子树需要被删除，我们将其节点数目也置为零，作为结果返回到上一层。最终根节点 0 对应的节点数目即为答案。

Python3

class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        def dfs(u):
            for v in g[u]:
                dfs(v)
                value[u] += value[v]
                counter[u] += counter[v]
            if value[u] == 0:
                counter[u] = 0

        g = defaultdict(list)
        for i, p in enumerate(parent):
            if p != -1:
                g[p].append(i)
        counter = [1] * nodes
        dfs(0)
        return counter[0]

Java

class Solution {
    private Map<Integer, List<Integer>> g;
    private int[] counter;
    private int[] value;

    public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
        g = new HashMap<>();
        for (int i = 0; i < nodes; ++i) {
            if (parent[i] != -1) {
                g.computeIfAbsent(parent[i], k -> new ArrayList<>()).add(i);
            }
        }
        this.value = value;
        counter = new int[nodes];
        Arrays.fill(counter, 1);
        dfs(0);
        return counter[0];
    }

    private void dfs(int u) {
        for (int v : g.getOrDefault(u, Collections.emptyList())) {
            dfs(v);
            value[u] += value[v];
            counter[u] += counter[v];
        }
        if (value[u] == 0) {
            counter[u] = 0;
        }
    }
}

C++

class Solution {
public:
    unordered_map<int, vector<int>> g;
    vector<int> counter;
    vector<int> value;

    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        for (int i = 0; i < nodes; ++i)
            if (parent[i] != -1)
                g[parent[i]].push_back(i);
        counter.resize(nodes, 1);
        this->value = value;
        dfs(0);
        return counter[0];
    }

    void dfs(int u) {
        for (int v : g[u])
        {
            dfs(v);
            value[u] += value[v];
            counter[u] += counter[v];
        }
        if (value[u] == 0) counter[u] = 0;
    }
};

Go

func deleteTreeNodes(nodes int, parent []int, value []int) int {
	g := make(map[int][]int)
	for i, p := range parent {
		if p != -1 {
			g[p] = append(g[p], i)
		}
	}
	counter := make([]int, nodes)
	for i := range counter {
		counter[i] = 1
	}
	var dfs func(u int)
	dfs = func(u int) {
		if vs, ok := g[u]; ok {
			for _, v := range vs {
				dfs(v)
				value[u] += value[v]
				counter[u] += counter[v]
			}
		}
		if value[u] == 0 {
			counter[u] = 0
		}
	}
	dfs(0)
	return counter[0]
}

...