ac solution code


  • 0

    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
        }
        return total
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.