Li Kou 2049: count the number of nodes with the highest score

2022 year 03 month 11 Japan Try to make a daily question

subject

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:

 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：

 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 .

Related Topics

• Trees
• Depth-first search
• Array
• Binary tree

Personal solution

Ideas ：

This question is to return to The highest score Node number , Then you have to calculate the score of each node , And the score of each node , Is the product of the following numbers , Include , The number of nodes in the left subtree under this node 、 The number of nodes in the right subtree under this node , And the total number of nodes - Change the node to the number of nodes in the tree following the node .

that , My problem solving steps are as follows ：

1. I gave it first according to the topic parents The array counts the direct child nodes of each node , Store it in map in .

2. according to map Use recursion to find the number of nodes in the subtree with each node as the root node , Deposit it in counts Array

3. Next, traverse to find the score of each node , And record the maximum score and the number of nodes

Here is java Code solution of ：

class Solution {
    
    //  Record the number of nodes in the subtree of each node as the root node 
    int[] counts;
    public int countHighestScoreNodes(int[] parents) {
    
        int size = parents.length;

        //  Record the direct child nodes of each node 
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < size; i++) {
    
            map.put(i, new ArrayList<>());
        }
        for (int i = 1; i < size; i++) {
    
            map.get(parents[i]).add(i);
        }

        //  Record the number of nodes in the tree where each child node is the root node 
        counts = new int[size];
        for (int i = 0; i < size; i++) {
    
            if (counts[i] > 0) {
    
                continue;
            }
            counts[i] = dfs(map.get(i), map);
        }

        //  Traverse and calculate the score of each node and count the results 
        long mul = 1;
        for (int num : map.get(0)) {
    
            mul *= counts[num];
        }
        int count = 1;
        for (int i = 1; i < size; i++) {
    
            long temp = 1;
            for (int num : map.get(i)) {
    
                temp *= counts[num];
            }
            temp *= (size - counts[i]);
            if (temp > mul) {
    
                mul = temp;
                count = 1;
            } else if (temp == mul) {
    
                count++;
            }
        }
        return count;
    }
    /** *  Calculate the number of nodes in the tree where each node is the root node  */
    private int dfs(List<Integer> list, Map<Integer, List<Integer>> map) {
    
        if (list.size() == 0) {
    
            return 1;
        }
        int count = 1;
        for (int i : list) {
    
            if (counts[i] > 0) {
    
                count += counts[i];
            } else {
    
                count += dfs(map.get(i), map);
            }
        }
        return count;
    }
}