aboutsummaryrefslogtreecommitdiff
path: root/count_nodes_highest_score.c
blob: 23cb6169e1a042b3af8d653bbbd9f37a50c93e39 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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
}