aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_nodes_highest_score.c73
-rw-r--r--count_nodes_highest_score.py47
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]))