# ac solution code

• Solution1. Level order BFS - time = O(n); space = O(n) - Cached Integer items

Difference from Q1: weight: from leaf to root. leaf = 1 (Q1: root = 1)

KEYS

• depth = deepestBranchToRoot(all branches) - RootToCurLevel (Not leaf to cur in current branch)
• Sum all previous items again for each level, to avoid calculating height

Explanation

• Level order BFS
• Sum all previous integers again in each deeper level: integer * depthFromDeepestLeaf
1. Base case: Enqueue items in input list
2. Loop through Queue:
• count = queue.count
• Dequeue one item
• if Integer, append to `prevSum`
• if list, enqueue items in list
• totalSum += prevSum
``````func depthSumInverse(_ list: [NestedInteger]) -> Int {
var total = 0, prevSum = 0
var queue = [NestedInteger]()
queue.append(contentsOf: list)              // 1. Base case: enqueue items in input nestedList

while !queue.isEmpty {                      // 2. Level order BFS:
let count = queue.count                 // 2-1. count
var levelSum = 0
for _ in 0..<count {
let cur = queue.removeFirst()       // 2-2. Dequeue: cur item
if cur.isInteger() {
levelSum += cur.getInteger()    // 2-3. Integer: sum of curLevel
} else {                            // 2-4: List: Next level - enqueue items in list
if cur.getList().count > 0 {    // Ignore empty list, otherwise it can be considered as deepest branch
queue.append(contentsOf: cur.getList())
}
}
}
prevSum += levelSum                     // 3-1. One level - Sum all previous integers <-- out of for loop
total += prevSum                        // 3-2. total = sum of all pre
}