LC: 1120. Maximum Average Subtree - spiralgo/algorithms GitHub Wiki

1120. Maximum Average Subtree

The Essence:

The average of some root can only be calculated and compared to its children's after the children are looked up. The children should then return their subtree size and their sum to their parent. At each node, the global maximum is thus: global = max(global, root's average, right average, left's average)

Details: The children can return the two values in an array of 2. They can also return their average as a 3. array element, or it can be recalculated at the root. For the first case, global maximum is a class variable. For the second, global maximum is the 3 element of the recursive search function applied to the root. The recursive search is structured as left-right-root, which corresponds to post-order traversal.