Daily classic

All rivers run into sea

describe

There is a binary tree rooted at 0 consisting of n nodes. The nodes are labeled from 0 to n – 1. You are given a 0-indexed integer array parents representing the tree, where parents[i] is the parent of node i. Since node 0 is the root, parents[0] == -1.

Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees.

Return the number of nodes that have the highest score.

Example 1:

Input: parents = [-1,2,0,2,0]
Output: 3
Explanation:
- The score of node 0 is: 3 * 1 = 3
- The score of node 1 is: 4 = 4
- The score of node 2 is: 1 * 1 * 2 = 2
- The score of node 3 is: 4 = 4
- The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.
Copy the code

Example 2:

Input: parents = [-1,2,0]
Output: 2
Explanation:
- The score of node 0 is: 2 = 2
- The score of node 1 is: 2 = 2
- The score of node 2 is: 1 * 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.
Copy the code

Note:

n == parents.length 2 <= n <= 10^5 parents[0] == -1 0 <= parents[i] <= n - 1 for i ! = 0 parents represents a valid binary tree.Copy the code

parsing

There exists a binary tree with root 0, consisting of n nodes. Nodes are marked from 0 to n-1. Parent [I] is the parent of node I. Parent [I] is the parent of node I. Since node 0 is the root node, parents[0] == -1. Each node has a score, and to find the score of a node, consider whether the node and its connected edges were deleted. The tree will become one or more non-null subtrees. The size of a subtree is the number of nodes in it. The fraction of a node is the product of the sizes of all of these subtrees. Returns the number of nodes with the highest score.

After removing a node, three parts will be generated in the mode: the number of nodes P in the upper part of the node, the number of left subtrees L and the number of right subtrees R of the node. P * L *r is the score of the current node. So this problem is essentially subtree nodes, we define a DFS function, return to the root node for the current node, its contains the nodes in the tree, in the middle of the recursive function, we can get by the left subtree nodes, right subtree nodes, node, the node number above, just make sure they are greater than zero, Multiply each other to get the score of the current node, and finally find the number of maximum scores.

answer

class Solution(object): def __init__(self): self.children = None self.result = {} def countHighestScoreNodes(self, parents): """ :type parents: List[int] :rtype: int """ N = len(parents) self.children = [[] for _ in range(N)] for i in range(N): if parents[i]! =-1: self.children[parents[i]].append(i) self.dfs(0); return self.result[max(self.result)] def dfs(self, root): count = 0 L = [] for node in self.children[root]: L.append(self.dfs(node)) count += L[-1] score = 1 if len(self.children)-1-count>0: score *= len(self.children)-1-count for s in L: if s>0: score *= s if score not in self.result: self.result[score] = 1 else: self.result[score] += 1 return count+1Copy the code

The results

Given the node in the Python online submission With the Highest Score. Memory Usage: Given in the Python online submissions for Count Nodes With the Highest Score.Copy the code

Original link: leetcode.com/problems/co…