Problem overview
The class Codec has two methods. serialize(_ root: TreeNode?) turns a binary tree, possibly empty, into a String. deserialize(_ data: String) takes such a string and returns the root of the same tree, with the same shape and the same value in every node. The format is up to you. The lesson provides the TreeNode class, with val, left, right and init(_ x: Int).
The tests serialize a tree with one Codec and rebuild it with another, so the string has to carry everything. For [1,2,3,null,null,4,5] this lesson's format produces 1,2,#,#,3,4,#,#,5,#,#, and reading it back gives the same tree.
Approach: preorder with a marker for every missing child
Values alone don't determine a tree: the same preorder list fits many shapes. The fix is to write a marker, #, for every missing child. Then the string says exactly where each subtree stops. A node's piece, followed by everything under its left child, followed by everything under its right child, forms a self-delimiting unit, and the reader never needs to guess.
The reader mirrors the writer. It takes the next piece. A # means an empty subtree. A number means a node, and its left subtree is whatever the next recursive read consumes, followed by its right subtree. Every piece is written once and read once, so both directions run in O(n).
Commas separate the pieces because values can be negative and have several digits: without separators, 12 followed by 3 would be read as one number.
Step by step
- The list of pieces. A property
values, an empty[String], is shared by both methods and their helpers. - Start fresh.
serializesetsvaluesto[], so each call builds its own list. - Write the tree. It calls the helper
writeonroot, which appends the pieces of the whole tree in preorder. - Glue the pieces.
values.joined(separator: ",")returns one string with a comma between neighbours. - The helper
write. It takes aTreeNode?and returns nothing. - Missing child.
guard let node = nodefails fornil. Theelseblock appends"#"and returns, since nothing is under an empty child. - The node. After the guard, append
String(node.val): the node comes before its subtrees. - Children. Call
writeonnode.left, then onnode.right. - The read position. A second property,
pos, starting at 0, is the index of the next piece to read. - Split the string. In
deserialize,data.split(separator: ",")cuts at the commas, and.map { String($0) }turns each part into aString. Store it invalues. - Reset the position to 0 and return what
read()gives. - The helper
read. It returns aTreeNode?: it reads one whole subtree that starts atpos. - Take a piece into
valueand moveposforward. - Empty subtree. If
valueis"#", returnnil. - Otherwise make a node from
Int(value)!, then setnode.leftandnode.rightwith two calls toread(), in that order, and return the node.
The solution in Swift
class Codec {
var values = [String]()
var pos = 0
func write(_ node: TreeNode?) {
guard let node = node else {
values.append("#")
return
}
values.append(String(node.val))
write(node.left)
write(node.right)
}
func serialize(_ root: TreeNode?) -> String {
values = []
write(root)
return values.joined(separator: ",")
}
func read() -> TreeNode? {
let value = values[pos]
pos += 1
if value == "#" {
return nil
}
let node = TreeNode(Int(value)!)
node.left = read()
node.right = read()
return node
}
func deserialize(_ data: String) -> TreeNode? {
values = data.split(separator: ",").map { String($0) }
pos = 0
return read()
}
}
The Swift details worth a closer look:
splitreturns substrings.data.split(separator: ",")gives an array ofSubstring, notString, which is why each part goes throughString($0). By defaultsplitleaves out empty parts; the format never has an empty piece, so that doesn't matter here.Int(value)!.Int(_:)on a string returns an optional,nilwhen the text isn't a number. A leading minus sign is fine:Int("-100")is-100. The!is safe because the code reaches it only for pieces thatserializewrote as numbers.- Order of evaluation. In
read,node.left = read()runs beforenode.right = read(), and each call moves the sharedpos. That order has to match the order inwrite. guardand early return. Theelseof aguardmust leave the scope, so thereturnthere is required, and it prevents the code below from touching a missing node.- State in properties.
valuesandposare properties of a class, so the recursive helpers share them without passing anything around.serializeanddeserializeboth reset what they use, so oneCodeccan be used for several trees.
Complexity
Time: O(n) for each method. write visits each node once and each missing child once, which is at most 2n + 1 pieces. joined and split each pass over the text once, and read consumes each piece once.
Space: O(n). The list of pieces and the string both grow with the number of nodes. The recursion is as deep as the tree, at most 400 levels in this lesson.
Edge cases and common mistakes
- The empty tree.
serialize(nil)returns"#", anddeserialize("#")returnsnil. The same code handles it, with no special case. - Leaving out the markers. Preorder values alone can't tell
[1,2]with 2 on the left from 2 on the right. Writing#for every missing child is what makes the string unambiguous. - No separator. Without commas, the pieces
12and3can't be told from1and23. Negative values need their-kept inside the piece. - Reading in a different order than writing. If
writedoes node, left, right, thenreadmust build the node, then the left subtree, then the right subtree. - Forgetting to reset
pos. Aposleft over from a previous call would start reading in the middle of the new list.
Testing
Serializing each tree and reading it back gives:
[1,2,3,null,null,4,5]becomes1,2,#,#,3,4,#,#,5,#,#and comes back as[1,2,3,null,null,4,5].[]becomes#and comes back as[].[-1,0,null,null,-100]becomes-1,0,#,-100,#,#,#and comes back unchanged.[1]becomes1,#,#.[1,2,null,3]becomes1,2,3,#,#,#,#and comes back unchanged.[5,null,6,null,7]becomes5,#,6,#,7,#,#and comes back unchanged.
