⚡Flashcard Drill➔
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

  1. The weight depends on the maximum depth, which is not known until the whole structure is seen.
  2. So do a level-by-level BFS, collecting the unweighted sum at each level.
  3. After the BFS, the number of levels is known, and level i (0-indexed) gets weight levels - i.
  4. An alternative single-pass approach accumulates total + running_sum at 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems