This problem was asked by Google.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = rightThe following test should pass:
node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'Solution
I wrote the solutions in Swift. Feel free to comment with your solution in the language of your choice.
First we need to translate the Python code into Swift.
The Node class.
public class Node {
var val: String
var left: Node?
var right: Node?
init(_ val: String){
self.val = val
}
}
Instead of using assert, we’re going to compare the values of the nodes using a simple if else statement.
if deserialize(s: serialize(root: root)).val == root.val { print("Berry Nice!")
} else { print("Oh, no!") }Now that we have our Node class and our test, we can move forward with the solution.
Swift has some nice protocols for encoding, decoding, and serialization in the Swift Standard Library. Unfortunately, our Node class does not conform to the protocol. Instead, I made my own encoder. It isn’t very secure; and I wouldn’t recommend using this to transmit important information over the Internet.
The serialize function.
func serialize(root: Node) -> Node {
var s: Node
var val = ""
var temp: Character
for char in root.val {
switch char {
case "1":
temp = "7"
case "2":
temp = "4"
case "7":
temp = "5"
case "a":
temp = "u"
case "z":
temp = "a"
case "D":
temp = "e"
case "v":
temp = "f"
case "I":
temp = "j"
case " ":
temp = "x"
default:
temp = char
}
val.append(temp)
}
s = Node(val)
return s
}
The deserialize function.
func deserialize(s: Node) -> Node {
var val = ""
var temp: Character
for char in root.val {
switch char {
case "7":
temp = "1"
case "4":
temp = "2"
case "5":
temp = "7"
case "u":
temp = "a"
case "z":
temp = "a"
case "e":
temp = "D"
case "f":
temp = "v"
case "j":
temp = "I"
case "x":
temp = " "
default:
temp = char
}
val.append(temp)
}
return Node(val)
}
Now let’s test it!
let root: Node = Node("David Inga")
if deserialize(s: serialize(root: root)).val == root.val {
print("Berry Nice!")
} else { print("Oh, no!") }
Berry Nice! It works.
This problem was provided by Daily Coding Problem. Get exceptionally good at coding interviews by solving one problem every day.
