There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. You are given a 2D integer array edges of length n - 1, where edges[i] = [aᵢ, bᵢ] indicates that there is an edge between nodes aᵢ and bᵢ in the tree.
A node is good if all the subtrees rooted at its children have the same size.
A subtree of treeName is a tree consisting of a node in treeName and all of its descendants.
Return the number of good nodes in the given tree.
fromtypingimportListclassStat:def__init__(self,val:int):self.val=valself.node_count=1self.good_count=0self.good=Trueself.child_node_count:int|None=NoneclassSolution:defcountGoodNodes(self,edges:List[List[int]])->int:n=len(edges)+1nodes=[set()for_inrange(n)]# nodes[i]: its neighbors (parent and children).fori,jinedges:nodes[i].add(j)nodes[j].add(i)stats=[Stat(None)]tasks=[(0,False)]whiletasks:r,ready=tasks.pop()node=Stat(r)parent=stats[-1]ifready:node=stats.pop()parent=stats[-1]elifr==0orlen(nodes[r])>1:# Non-leaf.tasks.append((r,True))forcinfilter(lambdai:i!=parent.val,nodes[r]):tasks.append((c,False))stats.append(node)continuenode.good_count+=1ifnode.goodelse0parent.node_count+=node.node_countparent.good_count+=node.good_countifparent.child_node_countisnotNoneandnode.node_count!=parent.child_node_count:parent.good=Falseparent.child_node_count=node.node_countreturnstats[0].good_count
评论需要 JavaScript。