LeetCode 2049. Count the number of nodes with the highest score -- traversal of the tree

2049. Count the number of nodes with the highest score
      Give you a tree with a root node of 0 Of Binary tree , It has a total of n Nodes , Node number is 0 To n - 1 . And give you a subscript from 0 The starting array of integers parents This tree , among parents[i] Is the node i Parent node . Due to the node 0 It's a root , therefore parents[0] == -1 .

Of a subtree size For the number of nodes in this subtree . Each node has an associated fraction . The way to find the score of a node is , All the nodes and the edges connected to it Delete , The rest are several Non empty subtree , Of this node fraction For all these subtrees The product of size .

Please return there The highest score Node number .

Example 1:

example-1

Input ：parents = [-1,2,0,2,0]
Output ：3
explain ：

• node 0 The score of is ：3 * 1 = 3
• node 1 The score of is ：4 = 4
• node 2 The score of is ：1 * 1 * 2 = 2
• node 3 The score of is ：4 = 4
• node 4 The score of is ：4 = 4
  The highest score is 4 , There are three nodes with scores of 4 （ They are nodes 1,3 and 4 ）.
  Example 2：
  

example-2

Input ：parents = [-1,2,0]
Output ：2
explain ：

• node 0 The score of is ：2 = 2
• node 1 The score of is ：2 = 2
• node 2 The score of is ：1 * 1 = 1
  The highest score is 2 , There are two nodes with a score of 2 （ They are nodes 0 and 1 ）.

Tips ：

n == parents.length
2 <= n <= 105
parents[0] == -1
about i != 0 , Yes 0 <= parents[i] <= n - 1
parents Represents a binary tree .

Answer key

Just count the size of the left and right subtrees of each node .

AC Code

class Solution {
    
public:
    typedef long long ll;
    ll L[100005],R[100005];// Record the size of the left and right subtrees of each node 
    int L_child[100005],R_child[100005];// Record the left and right child nodes of each node 
    int dfs(int root)//dfs Traverse the left and right subtrees of each node , Not including myself 
    {
    
        if(root==-1)return 0;
        L[root] = dfs(L_child[root]);
        R[root] = dfs(R_child[root]);
        return L[root] + R[root] + 1;//+1 Represents the root node itself 
    }
    int countHighestScoreNodes(vector<int>& parents) 
    {
    
        // The relationship between the node and the parent node is not declared , So the first thing that appears here is the left subtree , Then there is the right subtree 
        memset(L_child,-1,sizeof(L_child));
        memset(R_child,-1,sizeof(R_child));
        for(int i=0;i<parents.size();i++)
        {
    
            int u = parents[i];
            if(u!=-1)
            {
    
                if(L_child[u]==-1)
                L_child[u] = i;
                else
                R_child[u] = i;
            }
        }
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        dfs(0);
        ll mx = 0;
        for(int i=0;i<parents.size();i++)
        {
    
            ll L_ans=1,R_ans=1,parent_ans=1;
            if(L[i]!=0)L_ans = L[i];
            if(R[i]!=0)R_ans = R[i];
            if(parents.size()-L[i]-R[i]-1!=0)parent_ans = parents.size()-L[i]-R[i]-1;
            mx = max(mx, L_ans*R_ans*parent_ans);
        }
        int res = 0;
        for(int i=0;i<parents.size();i++)
        {
    
            ll L_ans=1,R_ans=1,parent_ans=1;
            if(L[i]!=0)L_ans = L[i];
            if(R[i]!=0)R_ans = R[i];
            if(parents.size()-L[i]-R[i]-1!=0)parent_ans = parents.size()-L[i]-R[i]-1;
            if(L_ans*R_ans*parent_ans==mx)
            res++;
        }
        return  res;
    }
};