难度: Medium
Submission
运行时间: 52 ms
内存: 18.0 MB
# from collections import defaultdict
# class Solution:
# def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
# g=defaultdict(list)
# # n=len(parent)
# for i,p in enumerate(parent):
# g[p].append(i)
# # ans=list(range(nodes))
# def dfs(i):
# # ret=value[i]
# # cnt=1
# st=[(value[i],1)]
# for j in g[i]:
# # cnt+=dfs[j][1]
# # ret+=dfs(j)[0]
# nxt=dfs[j]
# st.append(nxt)
# ret,cnt=0,0
# for r,c in st:
# ret+=r
# cnt+=c
# if ret==0:
# return 0,0
# return (ret,cnt)
# return dfs(0)[1]
# # # my:DFS+图哈希（refer 官解）
# from collections import defaultdict
# class Solution:
# def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
# g=defaultdict(list)
# # n=len(parent)
# for i,p in enumerate(parent):
# g[p].append(i)
# # ans=list(range(nodes))
# ans=[1]*nodes
# def dfs(i):
# # ret=value[i]
# # cnt=1
# # st=[(value[i],1)]
# for j in g[i]:
# # nxt=dfs[j]
# # st.append(nxt)
# dfs(j)
# value[i]+=value[j]
# ans[i]+=ans[j]
# if value[i]==0:
# ans[i]=0
# # return 0,0
# # return (ret,cnt)
# dfs(0)
# return ans[0]
# ### 官1：DFS+哈希
# class Solution:
# def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
# edges = {x: list() for x in range(nodes)}
# for x, p in enumerate(parent):
# if p != -1:
# edges[p].append(x)
# node_cnt = [1] * nodes
# def dfs(u):
# for v in edges[u]:
# dfs(v)
# value[u] += value[v]
# node_cnt[u] += node_cnt[v]
# if value[u] == 0:
# node_cnt[u] = 0
# dfs(0)
# return node_cnt[0]
# # # my:DFS+图哈希（后序遍历返回结果）
# from collections import defaultdict
# class Solution:
# def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
# g=defaultdict(list)
# # n=len(parent)
# for i,p in enumerate(parent):
# g[p].append(i)
# # ans=list(range(nodes))
# # ans=[1]*nodes
# def dfs(i):
# ret=value[i]
# cnt=1
# # st=[(value[i],1)]
# for j in g[i]:
# nr,nc=dfs(j) ### 这种写法可以通过
# ret+=nr
# cnt+=nc
# # dfs(j)
# # value[i]+=value[j]
# # ans[i]+=ans[j]
# if ret==0:
# return 0,0
# return (ret,cnt)
# return dfs(0)[1]
### 官2：拓扑排序 递归的归过程(就是根据出度为0的叶子节点更新父节点)
from collections import deque
class Solution:
def deleteTreeNodes(self,nodes,parent,value):
in_deg=[0]*nodes
for p in parent:
if p!=-1:
in_deg[p]+=1
node_cnt=[1]*nodes
q=deque()
for i in range(nodes):
if in_deg[i]==0:
q.append(i)
while q:
v=q.popleft()
if value[v]==0:
node_cnt[v]=0
u=parent[v]
if u!=-1:
value[u]+=value[v]
node_cnt[u]+=node_cnt[v]
in_deg[u]-=1
if in_deg[u]==0:
q.append(u)
return node_cnt[0]
Explain
本题解采用拓扑排序的方法来解决删除树节点的问题。首先，计算每个节点的入度，然后使用一个队列来存储所有入度为0的节点（即叶子节点）。从这些叶子节点开始，逐步向上更新其父节点的节点值和节点数量。如果某个节点的值更新后为0，则该节点以及其所有子节点都不应被计算在内，因此将其节点数量设置为0。最终，队列中会处理每个节点，直到到达根节点。这种方法从底部叶子节点向上至根节点逐层剪枝，直到所有的节点都被处理过。
时间复杂度: O(n)
空间复杂度: O(n)
# from collections import deque
class Solution:
def deleteTreeNodes(self, nodes, parent, value):
in_deg = [0] * nodes # 存储每个节点的入度
for p in parent:
if p != -1:
in_deg[p] += 1 # 计算入度
node_cnt = [1] * nodes # 初始化每个节点的计数为1
q = deque()
for i in range(nodes):
if in_deg[i] == 0:
q.append(i) # 将所有叶子节点加入队列
while q:
v = q.popleft()
if value[v] == 0:
node_cnt[v] = 0 # 如果节点值为0，设置节点计数为0
u = parent[v]
if u != -1:
value[u] += value[v] # 更新父节点的值
node_cnt[u] += node_cnt[v] # 更新父节点的计数
in_deg[u] -= 1 # 减少父节点的入度
if in_deg[u] == 0:
q.append(u) # 如果父节点入度为0，加入队列
return node_cnt[0] # 返回根节点的节点计数
Explore
拓扑排序是处理具有方向性从属关系的问题的一种有效方法，特别是在处理需要从子节点向父节点聚合信息的场景中。在此题中，从叶子节点开始向根节点聚合节点的值和计数信息，能够确保在处理每个节点时，其所有子节点的信息已经被完全处理和更新，这样可以有效地减少重复计算和回溯，提高效率。相比之下，DFS和BFS虽然也能实现节点的遍历，但在处理节点删除或值更新时，可能需要更复杂的回溯操作或多次遍历。
在题解中，当某个节点的值更新为0后，该节点以及其所有子节点应被视为在最终的节点计数中不再被包含。这是因为题目的目的是计算保留的有效节点的总数，节点值为0意味着这个节点及其子树不应被计入最终的统计结果中。因此，在实现中，节点值为0时会将该节点的节点计数设置为0，并且在更新父节点时，不再将这些节点的计数加到父节点上。
在题解的逻辑中，即使某个父节点的值在更新后变为0，其父节点的值和节点数量仍需要继续更新。这是因为父节点的值变为0是在加入子节点的值之后的结果，而其它子节点的值可能仍然需要加到这个父节点上。只有当处理到这个父节点本身，并发现其值为0时，才将其计数设置为0，并在后续的更新中不再计入其父节点的计数。
在代码实现中，首先识别所有入度为0的节点，即叶子节点，将它们加入队列。这些节点是没有子节点的，因此可以安全地开始处理它们。在处理过程中，每当一个节点被处理（即从队列中移除并更新其父节点的值和计数），其对应的父节点的入度会减少。当父节点的入度减少到0时，意味着该父节点的所有子节点都已处理完毕，此时将父节点加入队列。这个逐层处理保证了从叶子节点向上至根节点的正确更新顺序。