{"id":8646,"date":"2021-10-26T20:13:10","date_gmt":"2021-10-27T03:13:10","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8646"},"modified":"2021-10-26T20:19:43","modified_gmt":"2021-10-27T03:19:43","slug":"leetcode-2049-count-nodes-with-the-highest-score","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-2049-count-nodes-with-the-highest-score\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2049. Count Nodes With the Highest Score"},"content":{"rendered":"\n

There is a binary<\/strong> tree rooted at 0<\/code> consisting of n<\/code> nodes. The nodes are labeled from 0<\/code> to n - 1<\/code>. You are given a 0-indexed<\/strong> integer array parents<\/code> representing the tree, where parents[i]<\/code> is the parent of node i<\/code>. Since node 0<\/code> is the root, parents[0] == -1<\/code>.<\/p>\n\n\n\n

Each node has a score<\/strong>. To find the score of a node, consider if the node and the edges connected to it were removed<\/strong>. The tree would become one or more non-empty<\/strong> subtrees. The size<\/strong> of a subtree is the number of the nodes in it. The score<\/strong> of the node is the product of the sizes<\/strong> of all those subtrees.<\/p>\n\n\n\n

Return the number<\/strong> of nodes that have the highest score<\/strong><\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"example-1\"\/<\/figure>\n\n\n\n
Input:<\/strong> parents = [-1,2,0,2,0]\nOutput:<\/strong> 3\nExplanation:<\/strong>\n- The score of node 0 is: 3 * 1 = 3\n- The score of node 1 is: 4 = 4\n- The score of node 2 is: 1 * 1 * 2 = 2\n- The score of node 3 is: 4 = 4\n- The score of node 4 is: 4 = 4\nThe highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"example-2\"\/<\/figure>\n\n\n\n
Input:<\/strong> parents = [-1,2,0]\nOutput:<\/strong> 2\nExplanation:<\/strong>\n- The score of node 0 is: 2 = 2\n- The score of node 1 is: 2 = 2\n- The score of node 2 is: 1 * 1 = 1\nThe highest score is 2, and two nodes (node 0 and node 1) have the highest score.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == parents.length<\/code><\/li>
  • 2 <= n <= 105<\/sup><\/code><\/li>
  • parents[0] == -1<\/code><\/li>
  • 0 <= parents[i] <= n - 1<\/code> for i != 0<\/code><\/li>
  • parents<\/code> represents a valid binary tree.<\/li><\/ul>\n\n\n\n
    Solution: Recursion<\/strong><\/h2>\n\n\n\n
    Write a function that returns the element of a subtree rooted at node.<\/p>\n\n\n\n
    We can compute the score based on:
    1. size of the subtree(s)
    2. # of children<\/p>\n\n\n\n
    Root is a special case whose score is max(c[0], 1) * max(c[1], 1).<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countHighestScoreNodes(vector& parents) {\n    const int n = parents.size();\n    long high = 0;\n    int ans = 0;\n    vector> tree(n);\n    for (int i = 1; i < n; ++i)\n      tree[parents[i]].push_back(i);\n    function dfs = [&](int node) -> int {      \n      long c[2] = {0, 0};\n      for (int i = 0; i < tree[node].size(); ++i)\n        c[i] = dfs(tree[node][i]);\n      long score = 0;\n      if (node == 0) \/\/ case #1: root\n        score = max(c[0], 1l) * max(c[1], 1l);\n      else if (tree[node].size() == 0) \/\/ case #2: leaf\n        score = n - 1;\n      else if (tree[node].size() == 1) \/\/ case #3: one child\n        score = c[0] * (n - c[0] - 1);\n      else \/\/ case #4: two children\n        score = c[0] * c[1] * (n - c[0] - c[1] - 1);\n      if (score > high) {\n        high = score;\n        ans = 1;\n      } else if (score == high) {\n        ++ans;\n      }\n      return 1 + c[0] + c[1];\n    };\n    dfs(0);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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 of node i.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[77,177,17,28],"class_list":["post-8646","post","type-post","status-publish","format-standard","hentry","category-tree","tag-graph","tag-medium","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8646","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8646"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8646\/revisions"}],"predecessor-version":[{"id":8648,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8646\/revisions\/8648"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8646"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8646"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8646"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}