Swift solution - recursive, DFS, BFS


  • 0
    class Solution {
        static let null = "null"
        static let separator = ","
        
        func serialize_Rec(_ root: TreeNode?) -> String {
            var result = [String]()
            
            buildString(root, &result)
            
            return result.joined(separator: Solution.separator)
        }
        
        private func buildString(_ root: TreeNode?, _ result: inout [String]) {
            if let root = root {
                result.append(String(root.val))
                buildString(root.left, &result)
                buildString(root.right, &result)
            }
        }
        
        func deserialize_Rec(_ data: String) -> TreeNode? {
            let nodes = data.components(separatedBy: Solution.separator)
            
            return buildTree(nodes)
        }
    
        private func buildTree(_ nodes: [String]) -> TreeNode? {
            var nodes = nodes
            let val = nodes.removeFirst()
            
            if val == Solution.null {
                return nil
            }
            
            let node = TreeNode(Int(val)!)
            node.left = buildTree(nodes)
            node.right = buildTree(nodes)
            return node
        }
        
        func serialize_BFS(_ root: TreeNode?) -> String {
            guard let root = root else {
                return ""
            }
            
            var result = [String]()
            var queue = [TreeNode?]()
            
            queue.append(root)
            while !queue.isEmpty {
                let node = queue.removeFirst()
                if let node = node {
                    result.append(String(node.val))
                    queue.append(node.left)
                    queue.append(node.right)
                } else {
                    result.append(Solution.null)
                }
            }
            
            return result.joined(separator: Solution.separator)
        }
        
        func deserialize_BFS(_ data: String) -> TreeNode? {
            if data == "" {
                return  nil
            }
            
            let vals = data.components(separatedBy: Solution.separator)
            guard let rootVal = Int(vals[0]) else {
                return nil
            }
            let root = TreeNode(rootVal)
            var queue = [root]
            var i = 1
            
            while i < vals.count {
                let parent = queue.removeFirst()
                if vals[i] != Solution.null {
                    guard let val = Int(vals[i]) else {
                        return nil
                    }
                    let left = TreeNode(val)
                    parent.left = left
                    queue.append(left)
                }
                i += 1
                if vals[i] != Solution.null {
                    guard let val = Int(vals[i]) else {
                        return nil
                    }
                    let right = TreeNode(val)
                    parent.right = right
                    queue.append(right)
                }
                i += 1
            }
            
            return root
        }
        
        func serialize_DFS(_ root: TreeNode?) -> String {
            var root = root
            var result = [String]()
            var stack = [TreeNode]()
            
            while root != nil || !stack.isEmpty {
                if root != nil {
                    result.append(String(root!.val))
                    stack.append(root!)
                    root = root?.left
                } else {
                    result.append(Solution.null)
                    root = stack.removeLast()
                    root = root?.right
                }
            }
            
            return result.joined(separator: Solution.separator)
        }
        
        func deserialize_DFS(_ data: String) -> TreeNode? {
            if data.characters.count == 0 {
                return nil
            }
            
            let nodes = data.components(separatedBy: Solution.separator)
            let count = nodes.count
            guard let val = Int(nodes[0]) else {
                return nil
            }
            let root = TreeNode(val)
            var node = root
            var i = 1
            var stack = [node]
    
            while i < count {
                while i < count && nodes[i] != Solution.null {
                    guard let val = Int(nodes[i]) else {
                        return nil
                    }
                    node.left = TreeNode(val)
                    node = node.left!
                    stack.append(node)
                }
                while i < count && nodes[i] != Solution.null {
                    node = stack.removeLast()
                    i += 1
                }
                if i < count {
                    i += 1
                    guard let val = Int(nodes[i]) else {
                        return nil
                    }
                    node.right = TreeNode(val)
                    node = node.right!
                    stack.append(node)
                }
            }
            
            return root
        }
    }
    

Log in to reply
 

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