NeetCode #412LC-364MediumTrees
← Back to All Problems#412 · #364 · Nested List Weight Sum II(嵌套列表加权和 II)
📌 Problem Statement & Constraints
This is an interactive problem. You are given a nested list of integers where each element is an integer or a list. Return the sum of every integer multiplied by its weight, where the weight is
maxDepth - depth + 1 (the outermost level has the largest weight). Constraints: the total number of integers is at most 50; the nesting depth is at most 50.💡 Core Algorithmic Approaches
- The weight depends on the maximum depth, which is not known until the whole structure is seen.
- So do a level-by-level BFS, collecting the unweighted sum at each level.
- After the BFS, the number of levels is known, and level
i(0-indexed) gets weightlevels - i. - An alternative single-pass approach accumulates
total + running_sumat each level, which weights outer levels more without knowing the depth in advance.
💻 Benchmark Python3 Implementation
class Solution:
def depthSumInverse(self, nestedList: "List[NestedInteger]") -> int:
# BFS collecting the unweighted sum of each level
levels = []
cur = nestedList
while cur:
nxt = []
s = 0
for item in cur:
if item.isInteger():
s += item.getInteger()
else:
nxt.extend(item.getList())
levels.append(s)
cur = nxt
# level i (0-indexed, outermost first) has weight len(levels) - i
return sum(s * (len(levels) - i) for i, s in enumerate(levels))
# Single-pass variant: each level's sum is added to the total repeatedly
class Solution2:
def depthSumInverse(self, nestedList: "List[NestedInteger]") -> int:
total = 0
running = 0 # sum of all levels seen so far
cur = nestedList
while cur:
nxt = []
for item in cur:
if item.isInteger():
running += item.getInteger()
else:
nxt.extend(item.getList())
total += running # outer levels get counted more often
cur = nxt
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each element is processed once.
💾 Space Complexity
O(w) for the widest level.
⚠️ Interview Pitfalls & Follow-ups
- Assuming the weight is the depth: the weight is
maxDepth - depth + 1, so the outermost level has the largest weight -- the opposite of the standard nested-list weight sum. - Using recursion and computing the depth first, then summing: two passes; the BFS collects everything in one.
- Getting the level order backwards:
levels[0]is the outermost level, which gets the largest weight. - Forgetting that a level may contain only lists: its integer sum is 0, but it still counts as a level for the weighting.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.