aboutsummaryrefslogtreecommitdiff
path: root/count_nodes_highest_score.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-04 11:28:17 -0700
committerJack Sangdahl <[email protected]>2024-11-04 11:28:17 -0700
commit6c724702128b3ccdaed34a885daee80734da9de6 (patch)
tree3042e367f4cca54e3293e82e283619a43753ba88 /count_nodes_highest_score.py
parent8da32611366272579bbede5051d444d03c9e335c (diff)
downloadleetcode-6c724702128b3ccdaed34a885daee80734da9de6.tar.gz
leetcode-6c724702128b3ccdaed34a885daee80734da9de6.zip
2049. count nodes with the highest score
Diffstat (limited to 'count_nodes_highest_score.py')
-rw-r--r--count_nodes_highest_score.py47
1 files changed, 47 insertions, 0 deletions
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]))