***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