ac solution code


  • 0

    Solution1. Stack - time = O(1); space = O(deepestHeight)

    KEY: Iterative solution for NestedInteger - it's actually Queue

    • Solution: Stack
    1. push: items of curLevel
    2. pop: until meets Integer
    • Note:
    1. It's actually Queue: FIFO, so should push list.reversed()
    class NestedIterator  {
        private var list: [NestedInteger]
        private lazy var stack = [NestedInteger]()
        
        init(_ list: [NestedInteger]) {
            self.list = list
            stack.append(contentsOf: list.reversed())   // 1. Push: items of curLevel // <-- reversed
        }
        
        var hasNext: Bool {                             // 2. Pop: until meets Integer
            while !stack.isEmpty {
                let top = stack.last!                   // 2-1. Peek
                if top.isInteger() {                    // 2-2. Integer: return true
                    return true
                } else {                                // 2-3. List: Push - from end to start // <--
                    stack.removeLast()
                    stack.append(contentsOf: top.getList().reversed())
                }
            }
            return false
        }
        
        func next() -> Int? {
            guard hasNext else {return nil}
            return stack.removeLast().getInteger()
        }
    }
    

Log in to reply
 

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