LC: 364. Nested List Weight Sum II - spiralgo/algorithms GitHub Wiki

364. Nested List Weight Sum II:

The Essence:

The principal problem implied here is that, unlike the prequel problem, we can't know which value we should multiply an integer value with since the its anti-proportional to the depth. We can't simply calculate it without knowing the depth.

Details:

To handle this, there are 2 ways:

• Traverse the entire nested list and find the maximum depth.
• Sum all elements now knowing their difference to the depth.

• If the sum of the first layer is some value S, while traversing the nested list layer by layer, if the sum of this layers get continually accumulated to the total, then it would be equivalent to adding it anti-proportionally with its depth. This can be done using BFS and maintaining the size of the current layers.