Count Nodes With the Highest Score LeetCode solution in Java

1
class Solution {
2
  /**
3
   * Algorithm/Theory 1. An efficient first step is to build the tree. This way, we can post-order
4
   * traverse it and determine the product of non-empty subtrees 2. Use a simple Node[] array to map
5
   * node order/value to Node content. set node[0] to be the parent. loop from 1 to n and if the
6
   * current node[i] is null, set it as new node. If the parent is null, initialize node[parent[i]].
7
   * set node[parent[i]].left or .right to node[i], depending if left or right is already set. 3.
8
   * Continue post-order traversal. - if on a leaf, that leaf will make a score of total -1. Check
9
   * against the current highest score and set. Return 1 as that leaft has only 1 node - if not on a
10
   * leaf, apply post-oder to left and right. 4. After 3b) for each parent node, determine its
11
   * number of nodes from its subtree: 1 + left + right. 6. Once 5 is done, determine the highest
12
   * score that node will generate. This will be Math.max(1, onLeft) * Math.max(1, onRight) *
13
   * Math.max(1, (totalNodes - nrOfNodesFromSubtree)). Basically we are multiplying the remaining 3
14
   * groups of nodes that are formed from the removal of that node (left, right, above). Pay
15
   * attention to multiply with 1 (not with 0). The root will have no "above" nodes so total -
16
   * nodesOnSubtree will return 0.
17
   */
18
  public int countHighestScoreNodes(int[] parents) {
19
    Node[] nodes = buildTree(parents);
20
    long[] highestScore = {0, 0};
21
    countHighestScore(nodes[0], highestScore, parents.length);
22
    return (int) highestScore[1];
23
  }
24

25
  private int countHighestScore(Node node, long[] highestScore, int total) {
26
    if (node != null) {
27
      if (node.left == null && node.right == null) {
28
        // a leaf will have 1 node under(itself) and will produce a total nodes - 1 score.
29
        if (highestScore[0] == total - 1) {
30
          highestScore[1]++;
31
        } else if (highestScore[0] < total - 1) {
32
          highestScore[0] = total - 1;
33
          highestScore[1] = 1;
34
        }
35
        return 1;
36
      } else {
37
        // apply post-order and see how many nodes are left and right
38
        int onLeft = countHighestScore(node.left, highestScore, total);
39
        int onRight = countHighestScore(node.right, highestScore, total);
40
        int totalSubtree = onLeft + onRight + 1;
41
        // if left or right is null, replace it with 1, multiplication by 1
42
        long possibleScore =
43
            (long) (Math.max(1, onLeft)) * Math.max(onRight, 1) * Math.max(1, total - totalSubtree);
44
        if (highestScore[0] == possibleScore) {
45
          highestScore[1]++;
46
        } else if (highestScore[0] < possibleScore) {
47
          highestScore[0] = possibleScore;
48
          highestScore[1] = 1;
49
        }
50
        return totalSubtree;
51
      }
52
    }
53
    return 0;
54
  }
55

56
  private Node[] buildTree(int[] parents) {
57
    Node[] nodes = new Node[parents.length];
58
    nodes[0] = new Node();
59
    for (int i = 1; i < parents.length; i++) {
60
      // create current node
61
      if (nodes[i] == null) {
62
        nodes[i] = new Node();
63
      }
64
      // create parent node
65
      if (nodes[parents[i]] == null) {
66
        nodes[parents[i]] = new Node();
67
      }
68
      // link parent node left or right to this child node.
69
      if (nodes[parents[i]].left == null) {
70
        nodes[parents[i]].left = nodes[i];
71
      } else {
72
        nodes[parents[i]].right = nodes[i];
73
      }
74
    }
75
    return nodes;
76
  }
77

78
  private static class Node {
79
    Node left;
80
    Node right;
81
  }
82
}