Swift solution - PreOrder with Queue


  • 0
    class Codec {
        static let null = "null"
        static let separator = ","
        
        func serialize(_ root: TreeNode?) -> String {
            guard let root = root else {
                return Codec.null
            }
            
            var list = [String]()
            var stack = [TreeNode]()
            
            stack.append(root)
            while !stack.isEmpty {
                let node = stack.removeLast()
                list.append(String(node.val))
                if let rightNode = root.right {
                    stack.append(rightNode)
                }
                if let leftNode = root.left {
                    stack.append(leftNode)
                }
            }
            
            return list.joined(separator: Codec.separator)
        }
        
        func deserialize(_ data: String) -> TreeNode? {
            if data == Codec.null {
                return nil
            }
            
            let list = data.components(separatedBy: Codec.separator)
            var queue = [Int]()
            
            for item in list {
                if let val = Int(item) {
                    queue.append(val)
                }
            }
            
            return getNode(queue)
        }
        
        func getNode(_ queue: [Int]) -> TreeNode? {
            if queue.isEmpty {
                return nil
            }
            
            var queue = queue
            let root = TreeNode(queue.removeFirst())
            var smallerQueue = [Int]()
            
            while !queue.isEmpty && queue[0] < root.val {
                smallerQueue.append(queue.removeFirst())
            }
            
            root.left = getNode(smallerQueue)
            root.right = getNode(queue)
            
            return root
        }
    }
    

Log in to reply
 

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