This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!
Problems
Serialize and Deserialize Binary Tree
We have to serialize a given binary tree to string, and then deserialize the string to the former binary tree.
So let's start with thinking about how to traverse the tree.
Approach
(https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/)
For starters let's think about the above example.
In the above example, the output string is [1, 2, 3, null, null ,4, 5].
To traverse tree, BFS or DFS is useful and We have to think which one is better.
DFS is more adapted because it will be easier to deserialize than BFS because the order of node encoded on BFS is based on the linkage of nodes. If you know the other reason to use DFS or you think BFS is more adapted and know the reason why it is, please leave your comment about your opinion!
Solution
class Codec:
def serialize(self, root):
""" Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def encode(root, string):
""" a recursive helper function for the serialize() function."""
# check base case
if root is None:
string += 'None,'
else:
string += str(root.val) + ','
string = encode(root.left, string)
string = encode(root.right, string)
return string
return encode(root, '')
# Deserialization
class Codec:
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
def decode(l):
""" a recursive helper function for deserialization."""
if l[0] == 'None':
l.pop(0)
return None
root = TreeNode(l[0])
l.pop(0)
root.left = decode(l)
root.right = decode(l)
return root
data_list = data.split(',')
root = decode(data_list)
return root
Thank you for reading this article!
I always welcome your feedback, question, and idea.
Top comments (0)