Leetcode 834 - Sum of Distances in Tree [28/4/24]

Time Taken: More than 30 mins
Tag: LeetCode Hard

Could not solve this and had to refer to online resources.
Still slightly confusing for me to think about this question.

High-level Ideas:
findCount() function:
- For each node, find the count of number of nodes below it and including the node itself
- This is to help with the rebalancing step later, where we utilise this information
- Denote nodeCountsAndBelow[currNode] as the answer for “the count of number of nodes below it and including the node itself” for currNode

rebalance() function:
- We “rebalance” the tree such that for the answer of “sum of distances in tree of current node” that we are finding, we make current node the root node.
- Given we always know the final answer of the sum of distances in tree for the root node:
- Each time from the “new” root node (after rebalancing the tree), we can find the answer by taking the final answer of that of the previous root node (which is the parent node of this “new” root node, known from our assumption), and subtract difference from it
- difference refers to the difference in “sum of distances in tree of previous root node (parent node)” and “sum of distances in tree of new current root node”
- By visualising the “rebalancing”, we basically:
- Shift the entire subtree starting from currNode up, therefore the sum of distances is shortened by nodeCountsAndBelow[currNode]
- Shift the rest of the nodes down, therefore the sum of distances is increased by number of remaining nodes, which is the same as “n - nodeCountsAndBelow[currNode]”, where n is the total number of nodes.
- Putting these 2 together: difference = (n - nodeCountsAndBelow[currNode]) - nodeCountsAndBelow[currNode] = n - 2 * nodeCountsAndBelow[currNode]