Idea: I feel like this question is quite important and useful, for its wild range of skills and usage in real life.
The "#" is used to represent none (empty node); meanwhile,
"," works as a symbol to split the return string.
Breath first search works as the traversal method since we are able to use 2i+1 and 2i+2 as the pointer to its children.
The most crucial thing in deserialize is that left = 2*(i-num) + 1, where num is the number of "#" in front of data[i]. It could a little bit hard to think it out, but always remember the recursion in this equation.more
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: An object of TreeNode, denote the root of the binary tree.
This method will be invoked first, you should design your own algorithm
to serialize a binary tree which denote by a root node to a string which
can be easily deserialized by your own "deserialize" method later.
"""
def serialize(self, root):
# a return object
string =""
# work for bfs
queue = []
# when root is none
if not root:
return root
while True:
# root is str type
if isinstance(root, str):
string = string + "#" + ","
# queue is empty, jump out
if not queue:
string = string + "#" + ","
break
# queue is not empty, pop out next
else:
root = queue.pop(0)
continue
# root is TreeNode type
else:
string = string + str(root.val) + ","
# there is a non-empty left node
if root.left:
left = root.left
else:
left = "#"
# enqueue
queue.append(left)
# there is a non-empty right node
if root.right:
right = root.right
else:
right = "#"
# enqueue
queue.append(right)
# pop out next
root = queue.pop(0)
return string
"""
@param data: A string serialized by your serialize method.
This method will be invoked second, the argument data is what exactly
you serialized at method "serialize", that means the data is not given by
system, it's given by your own serialize method. So the format of data is
designed by yourself, and deserialize it here as you serialize it in
"serialize" method.
"""
def deserialize(self, data):
# when data is none
if not data:
return data
# number of "#"
num = 0
# listfy the data
data = data.split(",")
# build the head node
node = TreeNode(data[0])
# deposite root for return
root = node
# work for bfs
queue = []
for i in range(0,len(data)):
# grab the val
val = data[i]
# record the numbers of "#" and ignore it
if val == "#":
num +=1
continue
# do the math to have the left node position
l = 2*(i-num) + 1
val = data[l]
if val != "#":
left = TreeNode(val)
node.left = left
queue.append(left)
# do the math to have the right node position
r = 2*(i-num) + 2
val = data[r]
if val != "#":
right = TreeNode(val)
node.right = right
queue.append(right)
# queue is not empty, pop out next
if queue:
node = queue.pop(0)
# queue is empty, finish the loop
else:
break
return root
