diff options
-rw-r--r-- | count_nodes_highest_score.c | 73 | ||||
-rw-r--r-- | count_nodes_highest_score.py | 47 |
2 files changed, 120 insertions, 0 deletions
diff --git a/count_nodes_highest_score.c b/count_nodes_highest_score.c new file mode 100644 index 0000000..23cb616 --- /dev/null +++ b/count_nodes_highest_score.c @@ -0,0 +1,73 @@ +// 2049. Count Nodes With the Highest Score +#include "leetcode.h" + +/* + * 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 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 nodes is the product of the + * sizes of all those subtrees. return the number of nodes that have highest + * score. + */ + +int dfs(int **children, int *children_cnt, int parent_size, int parent, + unsigned long long *max, int *highest_score) { + if (!children || !max || !highest_score) + return 0; + int *child = children[parent]; + unsigned long long score = 0; + int grandchild_cnt[2] = {0, 0}; + for (int i = 0; i < children_cnt[parent]; i++) { + grandchild_cnt[i] = + dfs(children, children_cnt, parent_size, child[i], max, highest_score); + if (!score) + score = grandchild_cnt[i]; + else if (grandchild_cnt[i]) + score *= grandchild_cnt[i]; + } + + int subtree_nodes_num = grandchild_cnt[0] + grandchild_cnt[1] + 1; + int remaining_nodes_num = parent_size - subtree_nodes_num; + if (!score) + score = remaining_nodes_num; + else if (remaining_nodes_num) + score *= remaining_nodes_num; + if (score > *max) { + *max = score; + *highest_score = 1; + } else if (score == *max) + (*highest_score)++; + return subtree_nodes_num; +} + +int countHighestScoreNodes(int *parents, int parentsSize) { + if (!parents) + return 0; + unsigned long long max = 0; + int highest_score = 0; + int **children = (int **)calloc(parentsSize, sizeof(int *)); + int children_cnt[parentsSize]; + for (int i = 0; i < parentsSize; i++) { + children[i] = (int *)calloc(2, sizeof(int)); + children_cnt[i] = 0; + } + for (int i = 1; i < parentsSize; i++) { + if (children_cnt[parents[i]] >= 2) + continue; + children[parents[i]][children_cnt[parents[i]]++] = i; + } + dfs(children, children_cnt, parentsSize, 0, &max, &highest_score); + for (int i = 0; i < parentsSize; i++) + free(children[i]); + free(children); + return highest_score; +} + +int main() { + int p1[] = {-1, 2, 0, 2, 0}, p2[] = {-1, 2, 0}; + printf("%d\n", countHighestScoreNodes(p1, ARRAY_SIZE(p1))); // expect: 3 + printf("%d\n", countHighestScoreNodes(p2, ARRAY_SIZE(p2))); // expect: 2 +} diff --git a/count_nodes_highest_score.py b/count_nodes_highest_score.py new file mode 100644 index 0000000..42ba2cc --- /dev/null +++ b/count_nodes_highest_score.py @@ -0,0 +1,47 @@ +# 2049. Count Nodes With the Highest Score +from collections import defaultdict + +""" +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 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 nodes is the product of the +sizes of all those subtrees. return the number of nodes that have highest +score. +""" + + +class Solution(object): + def countHighestScoreNodes(self, parents): + """ + :type parents: List[int] + :rtype: int + """ + n = [[0] * 2 for _ in range(len(parents))] + d = defaultdict(list) + + def dfs(root): + if not d[root]: + return 1 + if len(d[root]) == 1: + n[root][0] = dfs(d[root][0]) + elif len(d[root]) == 2: + n[root][0] = dfs(d[root][0]) + n[root][1] = dfs(d[root][1]) + return n[root][0] + n[root][1] + 1 + + for i in range(1, len(parents)): + d[parents[i]].append(i) + total, ans = dfs(0), [] + for i, j in n: + ans.append(max(i, 1) * max(j, 1) * max(total - i - j - 1, 1)) + return ans.count(max(ans)) + + +if __name__ == "__main__": + obj = Solution() + print(obj.countHighestScoreNodes(parents=[-1, 2, 0, 2, 0])) + print(obj.countHighestScoreNodes(parents=[-1, 2, 0])) |