***Serialize and Deserialize Binary Tree (Leetcode 297) (DCP 3)
BFS Method
Problem Link: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
arr=[]
if(root is None):
return ""
q=[root]
while(len(q)>0):
curr=q.pop()
if(curr is None):
arr.append("#")
else:
arr.append(str(curr.val))
if(curr is not None):
q.insert(0,curr.left)
q.insert(0,curr.right)
return ",".join(arr)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if(data==""):
return None
arr=list(map(str,data.split(',')))
if(len(arr)==0):
return None
i=0
root=TreeNode(int(arr[i]))
i+=1
q=[]
q.insert(0,root)
while(len(q)>0):
curr=q.pop()
if(arr[i]=='#'):
curr.left=None
else:
curr.left=TreeNode(int(arr[i]))
q.insert(0,curr.left)
i+=1
if(arr[i]=='#'):
curr.right=None
else:
curr.right=TreeNode(int(arr[i]))
q.insert(0,curr.right)
i+=1
return root
Last updated