#2049
Count Nodes With the Highest Score
specialist · 835 · lc medium +31 · verified · 52.6% accepted · 1,184 likes · top 43%
Description
A binary tree with n nodes (labeled 0 to n - 1) is given via the parents array (parents[0] == -1). Each node's score is computed by removing that node and all incident edges, then multiplying the sizes of every resulting non-empty subtree component. Return the count of nodes that achieve 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.
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.
Code
1
2
3